问题
如果将01背包、完全背包、多重背包混合起来。应该怎么求解呢？
01背包与完全背包的混合
考虑到在01背包和完全背包中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。
伪代码如下：
for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-w[i]]+c[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-w[i]]+c[i]};
再加上多重背包
转二进制优化的01背包就好了。还有一种神奇的东西叫单调队列优化，然而我也不会，有兴趣可以自学一下。
混合三种背包问题
有一个旅行者有一个最多能装v公斤的背包，现有n件物品，他们的重量分别是w1,w2,w3...他们的价值分别是c1,c2..
有的物品只可以取一次，有的物品只可以取无限次，有的物品有上限，求价值最大和。
输入 背包容量m<=200,物品数量n<=30
从第二行每行三个整数 w,c,p;物重，价值，数量
P==0说明能取无数件
输出 最大值
样例 输入 输出
10 3 11
2 1 0
3 3 1
4 5 4
参考程序
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,m; int c[40],w[40],p[40]; int f[201]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&w[i],&c[i],&p[i]); for(int i=1;i<=n;i++) if(p[i]==0) for(int j=w[i];j<=m;j++) f[j]=max(f[j],f[j-w[i]]+c[i]); else for(int j=1;j<=p[i];j++) for(int k=m;k>=w[i];k--) f[k]=max(f[k],f[k-w[i]]+c[i]); printf("%d",f[m]); return 0; }
例4：题目描述
背包体积为V ,给出N个物品，每个物品占用体积为Vi,价值为Wi,每个物品要么至多取1件，要么至多取mi件（mi > 1） , 要么数量无限 ， 在所装物品总体积不超过V的前提下所装物品的价值的和的最大值是多少？
输入描述 ：
第一行两个数N,V,下面N行每行三个数Vi,Wi,Mi表示每个物品的体积，价值与数量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=-1表示数量无限
输出描述 ：
1个数Ans表示所装物品价值的最大值
样例输入
2 10
3 7 2
2 4 -1
样例输出
22
参考程序
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int v,n; int w[100],c[100],m[100]; int f[600]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d%d",&w[i],&c[i],&m[i]); for(int i=1;i<=n;i++) if(m[i]==-1) for(int j=w[i];j<=v;j++) f[j]=max(f[j],f[j-w[i]]+c[i]); else for(int j=1;j<=m[i];j++) for(int k=v;k>=w[i];k--) f[k]=max(f[k],f[k-w[i]]+c[i]); printf("%d",f[v]); return 0; }
原文：http://www.cnblogs.com/z360/p/6365864.html