背包问题(2)(多重背包,分组背包)


443 观看次数
1490 字数
3 评论

(该文章转自本人csdn,原链接https://blog.csdn.net/Shadowlove9/article/details/104868932)

1:即视感——多重背包(二进制优化)

:”师傅,有人下来战书,约我等明日决战,如何对敌?”*
我接过战书,只见上面写道:
      你瞅你领那个贵物,我告诉你,来沈阳,没你好果汁吃!
                                东百虎哥
?有人挑衅?冲了他!
这次,我们师徒二人潜入了沈阳大街好果汁饮料店。
只见货架上摆着各种各样、价值不一的饮料(是我们获得的价值,不是买饮料需要的价格哦),不过每种饮料的数目都有限。
(说人话,这个问题是:有n件物品,已知这n件物品的重量、价值、个数,求解将哪些物品装入背包使得价值总和最大。——多重背包问题)
:“来吧徒儿,为师考考你,你觉得怎么偷?”
你想了一下,说 :“感觉,像是介于01和完全中间的问题,不过这次有一个限制条件:个数有限。”
:“嗯,不错,老规矩,先简化一下问题,只看前四种饮料,然后写程序吧。”

i(编号)1234
w(每件的重量)3598
v(每件的价值)9941
c(每件的个数)3123

我们的背包最大容量p=20;
你想了想,动手在01背包的程序上改了改:

for(int i=1;i<=n;i++)
    for(int j=p;j>=0;j--)
        for(int k=1;k<=c[i];k++)
            if(j>=k*w[i])
                f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);
                    
运行结果:47

:“就问你这程序写的彳亍不彳亍!”
我说:“⑧太行。虽然结果没毛病,但是,作为一名有素养的盗贼,不光要准,还要快!我觉得三层循环不行,来,为师让它给力点。”
首先,我们来玩个游戏:把20,拆成依次增加的、多个2的n次方的和,如果到最后拆不出来,就直接加上它。
当然,这对你来说没什么难度,你很轻松的写了出来:22=2⁰+2¹+2²+2³+7。
现在,事情就变得神奇了起来。看一下2⁰,2¹,2²,2³,他们的组合,可以表示出任意小于等于2⁰+2¹+2²+2³数的和(不懂的话,把2⁰+2¹+2²+2³转换成二进制形式,你就明白了),而通过这些数和最后一个数字7,就能表示出16~22之间的所有数字了。
:“然后嘞?”
假设,有22件物品A,我们把这22件分成5组,每组分别有2⁰,2¹,2²,2³,7件,再把每一组都看成是一件新的物品,并且我们可以算出以上五件新的物品的价值和所占空间。于是我们可以通过这五件物品的组合,来得到这22件物品A的所有选取方案。
:“也就是说,对每一种物品进行分组,然后......对于分出来的所有组,就可以通过01背包来得到答案了!”
:“干得漂亮徒儿!”,我称赞到。:“顺便说一下,刚才把数字拆分的过程叫二进制优化哦。”
于是,你写出了代码:

#include<bits/stdc++.h>
using namespace std;
int f[3000],w[1000],v[1000];
int main()
{
    int n,p,a,b,c,num=0;//num即为最后进行01背包的个数
    cin>>n>>p;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c;//价值 重量 件
        for(int i=1;i<=c;i*=2)//二进制优化
        {
            v[++num]=a*i;
            w[num]=b*i;
            c-=i;
        }
        if(c)//c!=0,也就是最后拆不出来的数字
        {
            v[++num]=a*c;
            w[num]=b*c;
        }
    }
    for(int i=1;i<=num;i++)
        for(int j=p;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    cout<<f[p]<<endl;

    return 0;
}

(这里还有一种利用单调队列的优化方式,本菜鸡还没有具体学习,之后(也许)会补上的)
学会的话,去做题吧 洛谷P1776

———————————————这里是萌萌哒的分割线o( ̄▽ ̄)o————————————————

2:可口VS百事——分组背包

偷啊偷,偷啊偷......
:“等一下,李在赣神魔?”,我连忙打断了想往背包里装入百事可乐的你。
:“怎么了?”
:“你竟然不装可口,装百事?简直是偷界之耻!”
:“蛤?不会真的有人不喜欢百事吧,那可挺令人恶心的。”
&&……&!!!#¥!……&……&……&!@#@!!!!@#¥#&
一番嘴炮以后,我们意识到:人类之间的悲喜并不相通,就像是百事与可口无法互相理解。
大半夜的,两个人都想赶紧收工,于是折中一下——对于同一类型的饮料,只能选择一个牌子,即百事和可口只能二选一,选谁就看谁值得了。(这里我们认为,每种饮料只有1瓶)
(说人话,这个问题是:有n件物品,告诉你这n件物品的重量以及价值,将这些物品划分为k组,每组中的物品互相冲突,最多选一件,求解将哪些物品装入背包可使价值总和最大。——分组背包问题)

这里是数据:

i(编号)123456
w(每件的重量)234623
v(每件的价值)138989
num(属于哪组)112233

我们的背包最大容量p=10;
呵~~~~为师好困,这个问题不算难,这次就不用你出手了。
其实,它还是一个稍微复杂点的01背包(上一篇文章我提到过,一定要搞明白01背包)
来,复习一下状态转移方程:
在这里插入图片描述
哦当然,还有被我们用烂的降维简化版本:
在这里插入图片描述
回到刚才的问题。比起01背包的选不选择第i件物品,这个问题不过是变成了选不选第i组物品,选的话选哪件。
我们可以在01背包的基础上,进行一些改动。

for(int i=1;i<=n;i++)
    for(int j=p;j>=w[i];j--)
        f[j]=max(f[j],f[j-w[i]]+v[i]);    

首先,将第一层循环的件数,改成组数;
第二次循环不变;
再加上第三层循环:判断第i组的第k件是否选择。
修改完的代码变成:

for(int i=1;i<=num;i++)//num是一共有多少组
    for(int j=p;j>=0;j--)//p还是容量
        for(int k=0;k<=cc[i];k++)//这里的cc[i],是第i组中一共有几件物品
            if(j>=w[q[i][k]])//q[i][k],是第i组的第k件物品
                f[j]=max(f[j],f[j-w[q[i][k]]]+v[q[i][k]]);    

这个代码就是在01背包上又套了一层。
其实,仔细观察一下你会发现,它还是相当于:
在这里插入图片描述
又回到最初的起点 ~记忆中你青涩的脸 ~
所以说,01背包,是重中之重!
学会的话,去做题吧 洛谷P1757
一番愉悦的选择后,我们又偷了个盆满钵满,该收工了。
:“站住!”
角落里传来了一道声音......

欲知后事如何,请看下回分解...

———————————————这里是萌萌哒的分割线o( ̄▽ ̄)o————————————————
第二篇关于背包的文章,欢迎大佬们批评指正~
这里是上一篇的链接:01背包,01背包优化,完全背包 戳我戳我


评论区

3 条评论呢

0.五葉魔法書
2020 August 11th

注意一下文章的排版,然后可以把图片托管到oss上,优化网站的访问速度

1.Shadowlove
2020 August 11th @五葉魔法書

捕捉管宝√
(鬼畜的排版是年轻犯的错 有时间改了它==)

添加新评论