一、 问题描述
有n件物品，每件物品都只有一件，每件物品的重量为w[i],价值为v[i]，现在有一个容量为V的背包，问如何选取物品放入背包，使得背包内的物品的总价值最大？
此时，我们举个例子：设一共有4件物品，背包的容量为8，每件物品的质量和价值分别为 2 3，3 4，4 5，5 6，求该背包最大能装的物品的价值是多少？
二、问题解决
首先对于一个物品，我们对它的命令就只有两个，要么放入背包（就是1），要么不放进背包（就是0）。
那么我们设置一个二维数组dp[i][j]，用它来表示：当放入第 i 件物品，且空间为 j 时存放的物品的最大价值。
此时我们的 dp[i][j]=max(dp[ i - 1 ] [ j ] , dp [ i - 1 ][ j - w [ i ] ] + v [ i ]),前面的dp[ i - 1 ] [ j ]表示在不放第 i 件物品时的最大价值，后面的 dp [ i - 1 ][ j - w [ i ] ] + v [ i ] 表示在不放入这个物品时，背包刚好能放入该物品的重量 的 最大价值，再把该物品放入背包，再加上 v [ i ]，即放入该物品的最大价值。
#include<stdio.h> #include<stdlib.h> int w[105],v[105],dp[105][105]; int max(int a,int b) { if (a>b) return a; else return b; } int main() { int i,n,m,j,k,V; double b; scanf("%d%d",&n,&V); for (i=1;i<=n;i++) { scanf("%d%d",&w[i],&v[i]); } for (i=0;i<=n;i++) { for (j=1;j<=V;j++) { if (j<w[i]) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); printf("%d ",dp[i][j]); } printf("\n"); } return 0; }
话不多说，我们直接上图来解释：
但是实际上我们可以从上面的表格中看到，我们用二维数组存储了第一行的数据，但实际上只在第二行用到了第一行的数据，在这之后就没有再用了，所以第 i 行的数据只是在第 i+1行用到了，用完之后没有用放在数组里面也占用了极大地空间，所以我们使用一个“滚动数组”来实现这种操作。所谓的滚动数组就是利用一维数组，把第i+1行的数据覆盖在第i行上面，于是就变成了：
#include<stdio.h> #include<stdlib.h> int w[105],v[105],dp[105]; int max(int a,int b) { if (a>b) return a; else return b; } int main() { int i,n,m,j,k,V; double b; scanf("%d%d",&n,&V); for (i=1;i<=n;i++) { scanf("%d%d",&w[i],&v[i]); } for (i=1;i<=n;i++) { for (j=1;j<=V;j++) { if (j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); printf("%d ",dp[j]); } printf("\n"); } return 0; }
非常奇怪，为什么这样的结果和上面算出来的不一样呢？ 观察这里的数据我们可以看出，在计算dp [ 1 ] [ 4 ]时，是在原先放了一个w[1 ]的基础上再放一个w [ 1 ]，这样它就放了两次，不符合我们01背包的规则， 那么我们该怎么做呢？其实很简单，只需要从打到小放置就可以了，即从V开始一直到w [ i ] 为止，这样就很好的解决了这个问题，到此，01背包的问题也算是圆满完成了，以下附上代码：
#include<stdio.h> #include<stdlib.h> int w[105],v[105],dp[105]; int max(int a,int b) { if (a>b) return a; else return b; } int main() { int i,n,m,j,k,V; double b; scanf("%d%d",&n,&V); for (i=1; i<=n; i++) { scanf("%d%d",&w[i],&v[i]); } for (i=1; i<=n; i++) { for (j=V; j>=w[i]; j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } for (j=1; j<=V; j++) { printf("%2d ",dp[j]); } printf("\n"); } return 0; }
原文：https://www.cnblogs.com/ypw1131115630/p/12988766.html
