题目链接：1268
时间限制: 1000 ms ??? ??? 内存限制: 65536 KB
提交数: 40600 ??? 通过数: 21799
设有n�种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M�，今从n�种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M�，而价值的和为最大。
第一行：两个整数，M�(背包容量，M≤200�≤200)和N�(物品数量，N≤30�≤30)；
第2..N+12..w[i]+1行：每行二个整数Wi,Ci,表示每个物品的重量和价值。
仅一行，一个数，表示最大总价值。
10 4
2 1
3 3
4 5
7 9
max=12
? ? ? ? 了解背包问题
? ? ? ? 01背包，只能背一次，后面不能在背了
? ? ? ? 多重背包，可以背w[i]次
? ? ? ? 完全背包，可以背无限次。
? ? ? ? 来，我们先按多重背包的思想来做
? ? ? ? 比如f[5](多重背包的j是逆序判断的)
f[5]=max(f[5],f[3]+x[i]);
等等，你们有没有发现问题？
f[3]还没有被刷新就用上了，那么，该怎么办呢？
就要按顺序来判断了。
for(int j=1;j<=w[i];j++)
完全背包跟踪：
i=0,f[0],....f[5]=0;前0个人--价值=0?
i=1,前1个人,?????j=w[1]..<=c=5;!!只有01背包??
????j=2,f[2]=max(f[2]=0,f[2-w[1]]+v[1]=100,
????j=3,f[3]=max(f[3]=0,f[3-w[1]]+v[1]=f[1]+v[1]=100
????j=4,f[4]=max(f[4]=0,f[4-w[1]]+v[1]=f[4-2]+100=f[2]+100??!!重要
//j=4时，f[4]用到的f[2]是本行的f[2]=100,f[4]=100+100=200;?
//!!假设，j从大到小，那么j=4时,f[4]=f[2]+100,f[2]是上一行=0,f[4]=100错误?
????j=5;f[5]=max(f[5],f[5-w[1]]+v[1]=f[3]+100=200;
结果：i=1,f[0]=0;f[1]=0,f[2]=100,f[3]=100,f[4]=200,f[5]=200,
i=2,前2个人?j=w[2]=3..<=c=5;
??f[3]=max(f[3]=100,f[3-w[2]]+v[2]=f[0]+120=120)=120;??
??f[4]=max(f[4]=200,f[4-w[2]]+v[2]=f[1]+120=?120
??f[5]=max(f[5]=200,f[5-w[2]]+v[2]=f[2]+120=100+120=220=220?
?
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,c;
int w[1001],v[1001];
int f[50001];
int main()
{ int i,j;
cin>>n>>c;
for(i=1;i<=n;i++)
cin>>w[i];
for(i=1;i<=n;i++)
cin>>v[i];
for(i=1;i<=n;i++)//物品
for(j=w[i];j<=c;j++)//!!只有完全背包，是从小 到大
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[c];
return 0;
}
}
?不点赞关注收藏的暑假作业翻倍！
?