混合背包問題：
即 每個物品可能是 01背包，完全背包，多重背包等多種情況的組合。
( 01背包 )即物品中，有的是只有一個，要么放入，要么不放入。
(完全背包)物品中，某件物品可以放入任意多個。
(多重背包) 物品中，某件物品有個數(shù)量限制，不允許超過這些數(shù)量。
(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} ; //該數(shù)組表示是否為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]實質(zhì)上是表示的是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]實質(zhì)上是表示的是i-1次之前的值。
}
}
}
return f[V] ;
}
int main()
{
int temp = package() ;
cout<<temp<<endl ;
system("pause") ;
return 0 ;
}
三、 當01背包 ， 完全背包 和多重背包混合的時候的解法
此時的主要思路就是，先將多種背包轉(zhuǎn)換成01背包問題。即先把對應(yīng)系數(shù)數(shù)列的每個物品的個數(shù)
分解成一個一個的單個參數(shù)，然后即轉(zhuǎn)換成了 01背包和完全背包混合的情況。