背包心得

0/1背包(package.pas) Description  【问题描述】  一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn。若每种物品只有一件，求旅行者能获得最大总价值。  【输入格式】  第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；  第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。  【输出格式】  仅一行，一个数，表示最大总价值。  【样例输入】package.in  10 4  2 1  3 3  4 5  7 9  【样例输出】package.out 

12

i为背包的第几个   m为其中 m kg 可以装最多多少价值w[i]c[i] m=12345678910数据：104i=1011111111121201334=f[2]+f[3](2+3=m)55555333013556888845401355699101279

有表格可知 ，f[i][j] 最优是 f[i][j]=max(f[i-1][j],f[i-w[i-1][j-w[i]+c[i]);   (要么不选，要么选c[i]并加上f[i-1][j-w[i]))

#include<iostream> using namespace std; int w[10001],c[10001]; int f[1001][1001]; int main() { int m,n; cin>>m>>n; for(int i=1;i<=n;i++) cin>>w[i]>>c[i]; for(int i=1;i<=n;i++) for(int v=m;v>0;v--) if(w[i]<=v) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]); else f[i][v]=f[i-1][v]; cout<<f[n][m]; return 0; }

不过二维数组很容易溢出，用一位数组就可以了

优化上面程序，可以看出二维可以合并成一维：

f[v]=max(f[v],f[v-w[i]]+c[i]);

其中，for(v=m;v>=w[i];v++) 

因为 若从前面开始循环，c[i]会被再次使用，是错误的。

且要到w[i]就必须结束（我也不知原因，请大神指点）

参考代码：

#include<iostream> #include<cstdio> using namespace std; int main() { int i,v,n,m,c[10001],w[10001],f[10001]; memset(f,0,sizeof(f)); scanf("%d%d",&m,&n); for(i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(i=1;i<=n;i++) for(v=m;v>=w[i];v--) //必须要从m->w[i] f[v]=max(f[v],f[v-w[i]]+c[i]); printf("%d",f[m]); return 0; }