本文共 1884 字，大约阅读时间需要 6 分钟。
此条博客内容部分参考自
题目：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路：01背包问题的特点就是，每种物品仅有一件，可以选择放或者不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
基本上所有和背包相关的问题的方程都由它衍生出来。这个状态转移方程的具体含义大概就是：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品放或不放，那么就可以转化为一个只牵扯第i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
其中有一维和二维的代码解析：
首先是二维的：代码内有注释解释：#include#include //#include #include using namespace std;const int MAX=1010;int N,V;int f[MAX][MAX];int c[MAX],w[MAX]; //费用和价值int main(){ //首先输入对应的费用和价值 scanf("%d%d",&N,&V); for(int i=1;i<=N;i++) scanf("%d%d",&c[i],&w[i]); //第一个i指的是，第i件 for(int i=1;i<=N;i++) for(int v=0;v<=V;v++)//结合上一个循环，也就是把所有情况 ：第0件到第n件的容量为0到V的所有价值都选了进来。 { f[i][v]=f[i-1][v];//在没有选择取不取第i件的前提时，现在的价格是前i-1件 if(v>=c[i])//意思就是假设第i件可取 f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]);//那么就判断 } //刚开始不理解，为什么要进行这个循环，直接输出F[N][i]不行吗,代码测试之后发现，确实也可以 //int res=0; //for(int i=0;i<=V;i++)//f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值 //res=max(res,f[N][i]); printf("%d",f[N][V]);}
然后是一维的代码：
下面我们对空间复杂度进行优化，从上面的代码可以看到i从1到N，每次算出了二维数组f[i][0…V]的所有值。那么如果用一个数组f[0…V]，可否保证第i次循环结束后f[v]中表示的状态就是我们定义的f[i][v]呢？我们知道，我们的f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]的两个子问题递推而来的，事实上要求，在每次主循环中我们要求如下伪代码的顺序才能保证f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题推来的。
“也就是所谓的滚动数组”
其实就是在于二维数组中：f[i][v]=f[i-1][v] 这一部分，所以对于i来说，每一次都是前一次的叠加，其实本事是没有变的，（能理解最好，不能理解就时常看看） 并且是需要逆序的，二维数组是逆序正序都可以的#include#include #include using namespace std;const int MAX=1010;int N,V;int f[MAX];int c[MAX],w[MAX]; //费用和价值int main(){ scanf("%d%d",&N,&V); for(int i=1;i<=N;i++) scanf("%d%d",&c[i],&w[i]); for(int i=1;i<=N;i++) for(int v=V;v>=c[i];v--) f[v]=max(f[v],f[v-c[i]]+w[i]);//若v
转载地址：http://lkfen.baihongyu.com/