多重背包问题
一问题描述：
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
二 问题解决
该问题可以转换为01背包来计算，方法如下：
对于每一个n[i] 求取 n[i] - 2 * k + 1> 0的最大值 ，
将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。
使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。
当 n[i] = 13的时候，k为3时 ，13 - 2 ^ 3 +1 > 0 ，达到最大值。
对应的系数为 1 2 4 6 。
当 n[i] = 18的时候，k为4时 ，18 - 2 ^ 4 + 1 >0 ，达到最大值。
对应的系数为1 2 4 8 3 。
然后即转换为普通的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} ; //表示每一种物品的数量
int f[V + 1] ; //
vector <int> n_list ; //存储分解之后的每一个系数
vector <int> w_list ; //将分解之后的每一个系数，乘以原来的每一个价值
vector <int> c_list ; //将分解之后的每一个系数，乘以原来的每一个体积
void iniPackage() //将n[i]中的每一个数量，转换成每一个系数
{
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)) ; //求取每一个系数
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 ;
}