本文主要是介绍背包九讲——多重背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
多重背包，每件物品能选的数量有限制，最多c【i】个1.二进制优化：
二进制优化的思想还是很巧妙的，根据c【i】得到一组这样的数 2^0,2^1,2^2,2^3.....2^(k-1) , c-2^k+1 其中k是满足2^k小于c的最大值，就像c=7=111，2^k=100=4 ;
c=9=1001, 2^k=1000=8 ; c=8=1000 2^k=0100=4
得到这组数的目的是什么呢，
1到c之间的所有数都可以由这组数组合得到（选取相加），而从这组数里任意选任意个（每个数最多只能选一次）加在一起得到的数也必定是1~c这个闭区间内的
例如14=1110 他对应的这组数为：1，2，4，7 可以试一试，通过前三个组合可以得到1~7之间的所有数，而加上7就可以得到8~14之间的所有数，因此可以得到1~14之间的任何数，所以我们可以只对这组数逐一进行01背包，而不用从1到c都要01背包一次，算是把O（c）的部分优化成了O（logc）
void erjinzhi()
{int i,j,k,m;memset(dp,0,sizeof(dp));for(i=0;i<n;i++){for(k=1;k<<1<c[i];k<<=1){for(j=V;j>=k*v[i];j--){dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);}}m=c[i]-k+1;for(j=V;j>=m*v[i];j--){dp[j]=max(dp[j],dp[j-m*v[i]]+m*w[i]);}}
}2.单调队列优化
参考了这篇博客的思想 http://blog.csdn.net/flyinghearts/article/details/5898183 以及k爷的代码http://blog.csdn.net/lxy767087094/article/details/54730613，加上自己的理解
那篇博客大体思想讲的很好，实现过程是用了两个队列，一个辅佐队列，不易理解
struct node
{int num,value;
}que[100000];
int tail,head;
void push(int x,int y)
{while(tail>head&&que[tail-1].value<y){tail--;}que[tail].num=x;que[tail++].value=y;
}
void singlequeue()
{int i,d,j;memset(dp,0,sizeof(dp));for(i=0;i<n;i++){c[i]=min(c[i],V/v[i]);for(d=0;d<v[i];d++){head=tail=0;for(j=0;j<=(V-d)/v[i];j++){push(j,dp[j*v[i]+d]-j*w[i]);while(que[head].num<j-c[i]&&tail>head)head++;dp[j*v[i]+d]=que[head].value+j*w[i];}}}
}博客原址：http://blog.csdn.net/jerans/article/details/54916955
这篇关于背包九讲——多重背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
