多重背包問題
一問題描述：
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。
求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
二 問題解決
該問題可以轉(zhuǎn)換為01背包來計算，方法如下：
對于每一個n[i] 求取 n[i] - 2 * k + 1> 0的最大值 ，
將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。
使這些系數(shù)分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。
當 n[i] = 13的時候，k為3時 ，13 - 2 ^ 3 +1 > 0 ，達到最大值。
對應(yīng)的系數(shù)為 1 2 4 6 。
當 n[i] = 18的時候，k為4時 ，18 - 2 ^ 4 + 1 >0 ，達到最大值。
對應(yīng)的系數(shù)為1 2 4 8 3 。
然后即轉(zhuǎn)換為普通的01背包問題。
三代碼分析：
#include <iostream>
#include <vector.h>
#include <math.h>
using namespace std ;
const int V = 1000 ;
const int T = 5 ;
int w[T] = 
{5 , 10 , 8 , 15 , 20 } ; //表示每一種物品的價值
int c[T] = {20 , 30 , 40 ,40 ,100} ; //表示每一種物品的體積
int n[T] = {13 , 18 ,20 , 15 ,16} ; //表示每一種物品的數(shù)量
int f[V + 1] ; //
vector <int> n_list ; //存儲分解之后的每一個系數(shù)
vector <int> w_list ; //將分解之后的每一個系數(shù)，乘以原來的每一個價值
vector <int> c_list ; //將分解之后的每一個系數(shù)，乘以原來的每一個體積
void iniPackage() //將n[i]中的每一個數(shù)量，轉(zhuǎn)換成每一個系數(shù)
{
for(int i = 0 ; i < T ; i++)
{
int p = 1 ;
cout<<n[i]<<": ";
while(n[i] - pow(2 , p) + 1 >= 0)
{
cout<<pow(2 ,p - 1)<<" " ;
n_list.push_back(pow(2 , p-1)) ; //求取每一個系數(shù)
w_list.push_back(w[i] * pow(2 , p-1)) ; //
c_list.push_back(c[i] * pow(2 , p-1)) ;
p++ ;
}
int x = n[i] - pow(2 , p-1) + 1 ;
if( x > 0)
{
cout<<x<<" " ;
n_list.push_back(x) ;
w_list.push_back(w[i] * x) ;
c_list.push_back(c[i] * x) ;
}
cout<<endl ;
}
for(int i = 0 ; i <= V ;i++) //表示可以不用全裝滿
f[i] = 0 ;
}
int package()
{
iniPackage() ;
int size = n_list.size() ;
for(int i = 0 ; i < size ;i++)
{
for(int v = V ; v >= c_list[i] ; v--)
{
f[v] = max(f[v] , f[v - c_list[i]] + w_list[i]) ;
}
}
return f[V] ;
}
int main()
{
int max = package() ;
cout<<max<<endl ;
getchar() ;
return 0 ;
}