混合背包问题
有 N种物品和一个容量是 V 的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 si次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
- si=−1 表示第 i种物品只能用1次；
- si=0 表示第 ii 种物品可以用无限次；
- si>0表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
其实从大体上来看，背包问题其实只有01，完全两大问题。对于混合背包，分组背包，多重背包其实就是通过某种优化手段，将其映射到01和完全两大背包类型中。
例如，此题的混合背包问题，昨天我们做了多重背包问题，不同体积与价值的物品可以有不同的数量。我们采用了一种二进制优化的方法，将多重背包映射成为01背包，然后套用01的模板即可。
好的 ，那么我们开始举一反三，混合背包可以简化成什么问题。
我们从数量开始入手，对于有固定容积的背包来说，其实是不存在无穷这一概念的，也就是说物品的无穷相对于优先的背包容积来说，是不存在的。本质上，全是多重背包问题。
ok，明确了这一点后，我们就可以把此题当做多重背包来做，然后可以用二进制优化的方法进行转化成01背包。
代码如下：
#include
using namespace std ;
const int N = 10010 ;
int f[N] ;
int w[N] , v[N] ;
int main()
{
int n , m ;
cin >> n >> m ;
int cnt = 0 ;
for(int i = 1 ; i <= n ; ++i)
{
int a , b , c ;
cin >> a >> b >> c ;
if(c == -1)
{
cnt ++ ;
v[cnt] = a ;
w[cnt] = b ;
}
else if(c == 0)
{
c = m / a ;
int k = 1 ;
while(c >= k )
{
cnt ++ ;
v[cnt] = a * k ;
w[cnt] = b * k ;
c -= k ;
k *= 2 ;
}
if (c)
{
cnt ++ ;
v[cnt] = a * c;
w[cnt] = b * c ;
}
}
else
{
int k = 1 ;
while(c >= k)
{
cnt ++ ;
v[cnt] = a * k ;
w[cnt] = b * k ;
c -= k ;
k *= 2 ;
}
if(c)
{
cnt ++ ;
v[cnt] = a * c ;
w[cnt] = b * c ;
}
}
}
n = cnt ;
for(int i = 1 ; i <= n ; ++i)
{
for(int j = m ; j >= v[i] ; --j)
{
f[j] = max(f[j] , f[j-v[i]] + w[i]) ;
}
}
cout << f[m] << endl ;
return 0 ;
}
