湫湫系列故事——减肥记I

题目链接：

https://vjudge.net/contest/348156#problem/M

题面：

思路：

这与最简单的01背包不同的是这里面菜是种类，可以取无限次，所以就从01背包转换为完全背包，而代码与01背包之间的差距就是j从v[i]到a，而如果为01背包，j就是从w到v[i]，就这点差距，其他就是一样的模板套路，这可以作为一个例题来就完全背包。

参考代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{int n,m;while(scanf("%d",&n)!=EOF){int dp[100010]= {0},w[110],v[110];for(int i=0; i<n; i++)scanf("%d%d",&w[i],&v[i]);scanf("%d",&m);for(int i=0; i<n; i++){for(int j=v[i]; j<=m; j++)//从v[i]一直加到m就实现了可以多次使用的作用{dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}printf("%d\n",dp[m]);}return 0;
}