【动态规划】【背包】多重背包二进制优化（简单易懂）和【题解】——【洛谷P1776】宝物筛选

0.前言

欠的债总是要还的。

今天来把多重背包二进制优化补完。

建议先食用【动态规划】【背包】多重背包模型讲解（附C++代码实现）

1.思路解析

还是老样子，动态规划五步走。

好吧你们都很熟悉了那这里就只谈优化。

先把原本的代码贴出来。

#include<bits/stdc++.h>usingnamespacestd;#defineMAXM1010//m的数据范围，可根据题目修改#defineMAXN1010//n的数据范围，可根据题目修改//m表示背包的重量，n表示物品的数量,dp[j]表示当前重量上限为j时的最大价值intm,n,dp[MAXM],cnt;structobject{intweight,value;//储存每个物品的重量和价值object(int_w=0,int_v=0):weight(_w),value(_v){};}a[MAXN];intmain(){scanf("%d%d",&m,&n);for(inti=1;i<=n;i++){//输入n个物品intw,v,m;//存储当前物品的重量,价值和件数scanf("%d%d%d",&w,&v,&m);for(intj=1;j<=n;j++)a[++cnt]=object(w,v);//展开}for(inti=1;i<=cnt;i++)for(intj=m;j>=a[i].weight;j--)//枚举所有能装下a[i]的重量dp[j]=max(dp[j],dp[j-a[i].weight]+a[i].value);printf("%d\n",dp[m]);return0;}

看一下有哪里可以优化的。

状态转移？这已经是最朴素的01 背包 01背包01背包转移了。已经没有优化的余地了（至少现在是）。

输入输出？已经使用scanf,printf了，也优化不了了。

那该怎么办？我们就只可以优化铺平了。

可以发现，如果直接暴力展平，那么就会导致大量的重复计算。我们的目标就是将当前物品的个数m，拆解成几个数，并且能够表示0~m之间的所有数。

什么意思呢？比如m=3，可以拆成2+1，就是现将两个物品打包成一个大物品，它的价值和重量都是单个物品的2倍，1同理，就是单个的。或者m=4可以拆解成3+1或2+1+1或者更多。需要找到一个符合上面描述的序列。

那么我们就很容易联想到了二进制。我们拿9来举例。9的二进制形式是1001 = 1 ∗ 2 3 + 0 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 = 8 + 1 1001=1*2^3+0*2^2+0*2^1+1*2^0=8+11001=1∗23+0∗22+0∗21+1∗20=8+1。那么我们可以先把9 99拆成4 + 2 + 1 4+2+14+2+1，剩下的先不动。

那么如果加上4 44，就代表二进制中从右往左第三位被选取了，即100 2 100_21002​，否则就是没选取。其它的同理，比如加上2 22，就代表二进制中从右往左第二位被选取了，即10 2 10_2102​。

又容易想到，这样我们就能表示出0到7所有的数了。那还剩下2呢？直接放进去，不需要管了。

为什么呢？我们现在的问题就是要把剩下的8和9表示出来。很简单，2+6不就等于8 88吗？2+7不就等于9 99吗？

那么使用上面那个策略，我们就成功的用几个数字表示出来0~m了。

如果还是看不懂的同学可以自己尝试代数理解一下，或者在评论区提出自己的疑惑哦。我会尽力为你解答。

那么接下来就是如何编写代码的问题了。

我们首先从1开始尝试，每次*2来找到下一个二进制位对应的十进制数（代码中使用位运算代替，效率更快），并从m中减掉，放到a数组里面去。直到下一位需要的数比剩下的部分还大为止。

如果有剩余的部分，那么就直接放进去就行了，关键代码如下：

for(intj=1;j<=m;j<<=1){// 二进制展开a[++cnt]=object(v*j,w*j);m-=j;}if(m)a[++cnt]=object(v*m,w*m);// 还有剩下的

这段代码的时间复杂度成功降到了O ( W log ⁡ n ) O(W\log n)O(Wlogn)，可以通过此题。

2.AC代码

#include<bits/stdc++.h>usingnamespacestd;#defineMAXN100010// m的数据范围，可根据题目修改// cnt储存当前物品数量,dp[i]储存当前背包容量为j时的最大值intn,W,cnt=1,dp[MAXN];structobject{// 储存每一个物品的信息intv,w;// 价值和重量object(int_v=0,int_w=0):v(_v),w(_w){}}a[MAXN];intmain(){cin>>n>>W;for(inti=1;i<=n;i++){intv,w,m;cin>>v>>w>>m;for(intj=1;j<=m;j<<=1){// 二进制展开a[++cnt]=object(v*j,w*j);m-=j;}if(m)a[++cnt]=object(v*m,w*m);// 还有剩下的}for(inti=1;i<=cnt;i++)// 01背包for(intj=W;j>=a[i].w;j--)dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);cout<<dp[W];return0;}

最后，制作不易，希望大家多多点赞收藏，关注下微信公众号，谢谢大家的关注，您的支持就是我更新的最大动力！
公众号上会及时提供信息学奥赛的相关资讯、各地科技特长生升学动态、还会提供相关比赛的备赛资料、信息学学习攻略等。