最近要解决一个背包问题，查阅网上的文章后，摘取自己需要的记录下来，不定期补充理解内容。
注：参考文献中内容多来自《背包问题九讲》
1. 0-1背包（ZeroOnePack）
问题描述：有N件物品和一个容量为V的背包，（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
把这个过程理解下：在前i件物品放进容量v的背包时，
它有两种情况：
第一种是第i件不放进去，这时所得价值为:f[i-1][v]
第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]
（第二种是什么意思？就是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品）
最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。
1for i=1..N2 for v=V..03 f[v]=max{f[v],f[v-c[i]]+w[i]};
2. 完全背包（CompletePack）
问题描述：有N种物品和一个容量为V的背包，（每种物品都有无限件可用）第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
完全背包按其思路仍然可以用一个二维数组来写出：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
注意：0-1背包代码中内循环逆序，完全背包中代码内循环顺序，具体见参考文件1；
for i=1..N for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]}
3. 多重背包（MultiplePack）
问题描述：有N种物品和一个容量为V的背包。（第i种物品最多有n[i]件可用），每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
这里同样转换为01背包：
普通的转换对于数量较多时，则可能会超时，可以转换成二进制。
【参考文献1】http://www.cppblog.com/tanky-woo/archive/2010/07/31/121803.html
4. 多重背包问题求解
说明：以下内容和代码来自于参考文献二；
多重背包问题类似于完全背包问题，可以像完全背包一样作为0-1背包问题的扩展问题直接求解，也可以采用二进制拆分策略拆分为0-1背包问题求解；
方法一：直接求解，类似于完全背包问题。
#include <iostream> using namespace std; const int N = 3;//物品个数 const int V = 8;//背包容量 int Weight[N + 1] = {0,1,2,2}; int Value[N + 1] = {0,6,10,20}; int Num[N + 1] = {0,10,5,2}; int f[N + 1][V + 1] = {0}; /* f[i][v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Weight[i]] + K * Value[i]);其中1 <= k <= min(Num[i],V/Weight[i]) //初始化 f[i][0] = 0; f[0][v] = 0; */ int MultiKnapsack() { int nCount = 0; //初始化 for (int i = 0;i <= N;i++) { f[i][0] = 0; } for (int v = 0;v <= V;v++) { f[0][v] = 0; } //递推 for (int i = 1;i <= N;i++) { for (int v = Weight[i];v <= V;v++) { f[i][v] = 0; nCount = min(Num[i],v/Weight[i]);//是当前背包容量v，而不是背包的总容量 for (int k = 0;k <= nCount;k++) { f[i][v] = max(f[i][v],f[i - 1][v - k * Weight[i]] + k * Value[i]); } } } return f[N][V]; } int main() { cout<<MultiKnapsack()<<endl; system("pause"); return 1; }
方法二：拆分为0-1背包
一种是直接对每一件物品进行拆分成min（Num[i],V/Weight[i]）件，之后在拆分后的集合上进行0-1背包的求解；
另一种是二进制拆分，二进制拆分能保证对于0,,,Num[i]间的每一个整数，均可以用若干个系数的和表示。
对每i件物品，拆分的策略为：新拆分的物品的重量等于1件,2件,4件,..,(2^(k - 1)),Num[i] - (2^(k - 1))件，其中k 是满足Num[i] - 2^k + 1 > 0 的最大整数。
举例：某物品为13件，则其可以分成四件物品，其系数为1,2,4,6.这里k = 3。注意，
（1）最后一个物品的件数的求法和前面不同，其直接等于 该物品的最大件数 - 前面已经分配之和。
（2）分成的这几件物品的系数和为Num[i]，表明第i种物品取的件数不能多于Num[i]。
（3）如果第i个物品的重量Weight[i] * 物品的个数Num[i] >= 背包总重量V，可以不用拆分。
这里（3）的原因是：物品拆分后，其个数肯定增加，那么复杂度肯定上去。因此，我们可以选择性地对物品进行拆分，不用拆分的背包类似完全背包问题，可以调用完全背包函数求解；否则调用0-1背包函数求解；
#include <iostream> using namespace std; const int N = 3;//物品个数 const int V = 8;//背包容量 int Weight[N + 1] = {0,1,2,2}; int Value[N + 1] = {0,6,10,20}; int Num[N + 1] = {0,10,5,2}; int f[V + 1] = {0}; /* f[v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 f[v] = max(f[v],f[v - Weight[i]] + Value[i]); v的为逆序 */ void ZeroOnePack(int nWeight,int nValue) { for (int v = V;v >= nWeight;v--) { f[v] = max(f[v],f[v - nWeight] + nValue); } } /* f[v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 f[v] = max(f[v],f[v - Weight[i]] + Value[i]); v的为增序 */ void CompletePack(int nWeight,int nValue) { for (int v = nWeight;v <= V;v++) { f[v] = max(f[v],f[v - nWeight] + nValue); } } int MultiKnapsack() { int k = 1; int nCount = 0; for (int i = 1;i <= N;i++) { if (Weight[i] * Num[i] >= V) { //完全背包:该类物品原则上是无限供应， //此时满足条件Weight[i] * Num[i] >= V时， //表示无限量供应，直到背包放不下为止. CompletePack(Weight[i],Value[i]); } else { k = 1; nCount = Num[i]; while(k <= nCount) { ZeroOnePack(k * Weight[i],k * Value[i]); nCount -= k; k *= 2; } ZeroOnePack(nCount * Weight[i],nCount * Value[i]); } } return f[V]; } int main() { cout<<MultiKnapsack()<<endl; system("pause"); return 1; }
【参考文献2】http://blog.csdn.net/insistgogo/article/details/11176693