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

【动态规划】【背包】多重背包二进制优化简单易懂和【题解】【洛谷P1776】宝物筛选0.前言1.思路解析2.AC代码0.前言欠的债总是要还的。今天来把多重背包二进制优化补完。建议先食用【动态规划】【背包】多重背包模型讲解附C代码实现1.思路解析还是老样子动态规划五步走。好吧你们都很熟悉了那这里就只谈优化。先把原本的代码贴出来。#includebits/stdc.husingnamespacestd;#defineMAXM1010//m的数据范围可根据题目修改#defineMAXN1010//n的数据范围可根据题目修改//m表示背包的重量n表示物品的数量,dp[j]表示当前重量上限为j时的最大价值intm,n,dp[MAXM],cnt;structobject{intweight,value;//储存每个物品的重量和价值object(int_w0,int_v0):weight(_w),value(_v){};}a[MAXN];intmain(){scanf(%d%d,m,n);for(inti1;in;i){//输入n个物品intw,v,m;//存储当前物品的重量,价值和件数scanf(%d%d%d,w,v,m);for(intj1;jn;j)a[cnt]object(w,v);//展开}for(inti1;icnt;i)for(intjm;ja[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之间的所有数。什么意思呢比如m3可以拆成21就是现将两个物品打包成一个大物品它的价值和重量都是单个物品的2倍1同理就是单个的。或者m4可以拆解成31或211或者更多。需要找到一个符合上面描述的序列。那么我们就很容易联想到了二进制。我们拿9来举例。9的二进制形式是1001 1 ∗ 2 3 0 ∗ 2 2 0 ∗ 2 1 1 ∗ 2 0 8 1 10011*2^30*2^20*2^11*2^08110011∗230∗220∗211∗2081。那么我们可以先把9 99拆成4 2 1 421421剩下的先不动。那么如果加上4 44就代表二进制中从右往左第三位被选取了即100 2 100_21002​否则就是没选取。其它的同理比如加上2 22就代表二进制中从右往左第二位被选取了即10 2 10_2102​。又容易想到这样我们就能表示出0到7所有的数了。那还剩下2呢直接放进去不需要管了。为什么呢我们现在的问题就是要把剩下的8和9表示出来。很简单26不就等于8 88吗27不就等于9 99吗那么使用上面那个策略我们就成功的用几个数字表示出来0~m了。如果还是看不懂的同学可以自己尝试代数理解一下或者在评论区提出自己的疑惑哦。我会尽力为你解答。那么接下来就是如何编写代码的问题了。我们首先从1开始尝试每次*2来找到下一个二进制位对应的十进制数代码中使用位运算代替效率更快并从m中减掉放到a数组里面去。直到下一位需要的数比剩下的部分还大为止。如果有剩余的部分那么就直接放进去就行了关键代码如下for(intj1;jm;j1){// 二进制展开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代码#includebits/stdc.husingnamespacestd;#defineMAXN100010// m的数据范围可根据题目修改// cnt储存当前物品数量,dp[i]储存当前背包容量为j时的最大值intn,W,cnt1,dp[MAXN];structobject{// 储存每一个物品的信息intv,w;// 价值和重量object(int_v0,int_w0):v(_v),w(_w){}}a[MAXN];intmain(){cinnW;for(inti1;in;i){intv,w,m;cinvwm;for(intj1;jm;j1){// 二进制展开a[cnt]object(v*j,w*j);m-j;}if(m)a[cnt]object(v*m,w*m);// 还有剩下的}for(inti1;icnt;i)// 01背包for(intjW;ja[i].w;j--)dp[j]max(dp[j],dp[j-a[i].w]a[i].v);coutdp[W];return0;}最后制作不易希望大家多多点赞收藏关注下微信公众号谢谢大家的关注您的支持就是我更新的最大动力公众号上会及时提供信息学奥赛的相关资讯、各地科技特长生升学动态、还会提供相关比赛的备赛资料、信息学学习攻略等。