混合背包问题：
即 每个物品可能是 01背包，完全背包，多重背包等多种情况的组合。
( 01背包 )即物品中，有的是只有一个，要么放入，要么不放入。
(完全背包)物品中，某件物品可以放入任意多个。
(多重背包) 物品中，某件物品有个数量限制，不允许超过这些数量。
(1)对于完全背包 和 01背包问题可以简单地组合
当判断该物品是01背包的时候，将体积从大到小递减运算。
当判断物品是完全背包的时候，将体积从小到大递增运算。
二 代码分析：
下面的代码是 01背包 和 完全背包组合的情况
#include <iostream>
using namespace std ;
const int V = 1000 ; //总的体积
const int T = 5 ; //物品的种类
int f[V+1] ;
int w[T] = 
{8 , 10 , 4 , 5 , 5}; //价值
int c[T] = {600 , 400 , 200 , 200 , 300}; //每一个的体积
int all[T] = {1 , 0 , 0 ,1 , 1} ; //该数组表示是否为01物品，若为1则为01物品。为0则表示为完全背包物品
const int INF = -66536 ;
int package()
{
for(int i = 0 ; i <= V ;i++) //条件编译，表示背包可以不存储满
f[i] = 0 ;
for(int i = 0 ; i < T ; i++)
{
if(all[i]) //如果该物品为01选择的化
{
for(int v = V ; v >= c[i] ;v--) //必须全部从V递减到0
{
f[v] = max(f[v-c[i]] + w[i] , f[v]) ; //此f[v]实质上是表示的是i-1次之前的值。
}
}
else //如果该物品为完全背包选择
{
for(int v = c[i] ; v <= V ;v++) //必须全部从V递减到0
{
f[v] = max(f[v-c[i]] + w[i] , f[v]) ; //此f[v]实质上是表示的是i-1次之前的值。
}
}
}
return f[V] ;
}
int main()
{
int temp = package() ;
cout<<temp<<endl ;
system("pause") ;
return 0 ;
}
三、 当01背包 ， 完全背包 和多重背包混合的时候的解法
此时的主要思路就是，先将多种背包转换成01背包问题。即先把对应系数数列的每个物品的个数
分解成一个一个的单个参数，然后即转换成了 01背包和完全背包混合的情况。