多重背包:
hdu 2191 珍惜现在，感恩生活 多重背包入门题
使用将多重背包转化为完全背包与01背包求解；
对于w*num>= V这时就是完全背包，完全背包为何只与01背包在循环上不同，因为01背包，每个物品只能取一次，所以要逆序；而完全背包，每个物品的数量无限多个，这就需要建在在之前已经取到了当前要取的基础之上；
同时01背包使用二进制优化处理；即使用二进制表示最优的可取值；
二进制优化的技巧:1,2,4,...,2k−1,n[i]−2k +1(循环之外)，且k是满足n[i]−2k +1 > 0的最大整数。例如，如果n[i]为13，就将这种 物品分成系数分别为1,2,4,6的四件物品。这种方法也能 保证对于0..n[i]间的每一个整数(证明可以分0..2k-1和2k..n[i]两段来分别讨论得出);
#include<bits/stdc++.h>
using namespace std;
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define inf 0x3f3f3f3f
int f[],V;
void ZeroOnePack(int w,int c)
{
for(int v = V;v >= w;v--)
f[v] = max(f[v],f[v-w]+c);
}
void CompletePack(int w,int c)
{
for(int v = w;v <= V;v++)
f[v] = max(f[v],f[v-w]+c);
}
void MultiPack(int w,int c,int num)
{
if(w*num >= V)
CompletePack(w,c);
else{
for(int k = ;k < num;k <<= ){
ZeroOnePack(w*k,k*c);// 二进制优化可取的数目;01背包只是看当前这件物品取与不取;
num -= k;
}
ZeroOnePack(w*num,c*num);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
int m,w,c,num;
MS0(f);
scanf("%d%d",&V,&m);
rep1(i,,m){// 在线即可
scanf("%d%d%d",&w,&c,&num);
MultiPack(w,c,num);
}
printf("%d\n",f[V]);
}
}