用f[i]记录当背包容量为i时，最大的重量。
那么初始状态所有f[i]=0，一个物品一个物品考察，从容量大的背包开始到容量为1的背包结束，这时所有容量小的背包肯定都还没有放入该物品，这时原有的f[i]值如果小于f[i-pi]+pi,
也就是未放这物品和放这物品后的容量值做比较，发现放这物品后总的容量值增大了，就放这物品。
推荐看背包九讲，网上有下载，写得很好
View Code
1 #include <cstdio> 2 int f[13000];//f[i]的值为背包容量为i时得到的最大价值 3 int w[3500]; 4 int d[3500]; 5 int main() 6 { 7 int n,m; 8 scanf("%d%d",&n,&m);//n为物品数量，m为背包能容纳的种量 9 for(int i=0; i< n; i++) 10 scanf("%d%d",&w[i],&d[i]);//w[i]为物品的重量，d[i]为价值 11 for(int i= 0; i < n; i++)//依次去试放每种物品 12 { 13 for(int k = m ; k > 0; k--)//从容量大的背包开始试 14 { 15 if(w[i] > k) continue; //物品重量大于背包容量，不能放 16 int t=f[k-w[i]] + d[i]; 17 if(f[k] < t)//物品放进去后，比不放得到的价值更大，那么放进去该物品 18 f[k] = t; 19 } 20 } 21 printf("%d\n",f[m]); 22 return 0; 23 }