A281.小伟的购物计划题解

背包问题，虽然很水，但能对。

#include<bits/stdc++.h>
using namespace std;
int n;//件数
int m;//容量
int w[1111];//重量
int v[1111];//价值
int f[1111][33333];//背包现在容量
int main()
{
cin>>m;//输入
cin>>n;//输入
for(int i=1;i<=n;i++)
{
cin>>w[i];
cin>>v[i];
v[i]*=w[i];
}
for(int i=1;i<=n;i++)//第几件
{
for(int j=0;j<=m;j++)//第i件物品的重量
{
f[i][j]=f[i-1][j];//答案等于前一件
if(j-w[i]>=0)//如果装得下
{
f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);//答案等于(现在的答案 ，[前一件][容量-物品容量]) 哪个更大
}
}
}
cout<<f[n][m];//输出答案
return 0;
}