多重背包:
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]两段来分别讨论得出);
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#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[110],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 = 1;k < num;k <<= 1){ 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,1,m){// 在线即可 scanf("%d%d%d",&w,&c,&num); MultiPack(w,c,num); } printf("%d ",f[V]); } }