单调队列优化的背包问题[通俗易懂]

单调队列优化的背包问题[通俗易懂]对于背包问题,经典的背包九讲已经讲的很明白了,本来就不打算写这方面问题了。但是吧。我发现,那个最出名的九讲竟然没写队列优化的背包。。。。那我必须写一下咯嘿嘿,这么好的思想。我们回顾一下背包问题吧。01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总…

大家好,又见面了,我是你们的朋友全栈君。

对于背包问题,经典的背包九讲已经讲的很明白了,本来就不打算写这方面问题了。

但是吧。

我发现,那个最出名的九讲竟然没写队列优化的背包。。。。

那我必须写一下咯嘿嘿,这么好的思想。

 

我们回顾一下背包问题吧。

 

01背包问题 

题目 
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 

f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 

就是说,对于本物品,我们选择拿或不拿

比如费用是3.

相关图解:

单调队列优化的背包问题[通俗易懂]

我们求表格中黄色部分,只和两个黑色部分有关

拿了,背包容量减少,我们价值加上减少后最大价值。

不拿,最大价值等于没有这件物品,背包不变,的最大价值。

完全背包问题 

题目 
有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 

基本思路 
这个问题非常类似于01背包问题,所不同的是每种物品有无限件。

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

图解:

单调队列优化的背包问题[通俗易懂]

因为我们拿了本物品还可以继续拿无限件,对于当前物品,无论之前拿没拿,还可以继续拿,所以是f[i][v-c[i]]+w[i]

 

换一个角度说明这个问题为什么可以f[i][v-c[i]]+w[i],也就是同一排。

单调队列优化的背包问题[通俗易懂]

其实是这样的,我们对于黄色部分,也就是当前物品,有很多种选择,可以拿一个,两个。。。一直到背包容量不够了。

也就是说,可以不拿,也就是J1,可以拿一个,也就是G1+w[i],也可以拿两个,也就是D1+2w[i],拿三个,A1+3w[i]。

但是我们看G2,G2其实已经是之前的最大了:A1+2w[i],D1+w[i],G1他们中最大的,对么?

既然G2是他们中最大的。

我们怎么求J2?

是不是只要求G2+w[i]和J1的最大值就好了。

因为G2把剩下的情况都保存好了。

 

多重背包问题 (正文)

题目 
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 

 

和之前的完全背包不同,这次,每件物品有最多拿n[i]件的限制。

思路一:我们可以把物品全都看成01背包:比如第i件,我们把它拆成n[i]件一样的单独物品即可。

思路二:思路一时间复杂度太高。利用二进制思路:一个n位二进制,能表示2^n种状态,如果这些状态就是拿了多少物品,我们可以把每一位代表的数都拿出来,比如n[i]=16,我们把它拆成1,2,4,8,1,每一堆物品看成一个单独物品。

为什么最后有个一?因为从0到16有十七种状态,四位不足以表示。我们最后补上第五位1.

把拆出来的物品按01背包做即可。

思路三:我们可以利用单调队列:

https://blog.csdn.net/hebtu666/article/details/82720880

单调队列优化的背包问题[通俗易懂]

再回想完全背包:为什么可以那么做?因为每件物品能拿无限件。所以可以。而多重背包因为有了最多拿多少的限制,我们就不敢直接从G2中拿数,因为G2可能是拿满了本物品以后才达到的状态 。

比如n[i]=2,如果G2的状态是2w[i],拿了两个2物品达到最大值,我们的J2就不能再拿本物品了。

如何解决这个问题?就是我给的网址中的,双端单调队列

利用窗口最大值的思想。

大家想想怎么实现再看下文。

 

发现问题了吗?

单调队列优化的背包问题[通俗易懂]

我们求出J2以后,按原来的做法,是该求K2的,但是K2所需要的信息和J2完全不同,红色才是K2可能需要的信息。

所以我们以物品重量为差,先把黑色系列推出来,再推红色系列,依此类推。

这个例子就是推三次,每组各元素之间差3.

这样就不会出现构造一堆单调队列的尴尬情况了。

在代码中继续详细解释:

//输入
int n;
int W;
int w[MAX_N];
int v[MAX_N];
int m[MAX_N];

 

int dp[MAX_N+1];//压空间,本知识参考https://blog.csdn.net/hebtu666/article/details/79964233
int deq[MAX_N+1];//双端队列,保存下标
int deqv[MAX_N+1];//双端队列,保存值

队列存的就是所有上一行能取到的范围,比如对于J2,队列里存的就是G1-w[i],D1-2w[i],A1-3w[i]等等合法情况。(为了操作方便都是j,利用差实现最终的运算)

他们之中最大的就是队头,加上最多存储个数就好。

 

 

单调队列优化的背包问题[通俗易懂]

 

void solve()
{
    for(int i=0;i<n;i++)//参考过那个网址第二题应该懂
    {
        for(int a=0;a<w[i];a++)//把每个分组都打一遍
        {
            int s=0;//初始化双端队列头尾
            int t=0;
            for(int j=0;j*w[i]+a<=W;j++)//每组第j个元素
            {
                int val=dp[j*w[i]+a]-j*v[i];
                while(s<t && deqv[t-1]<=val)//直到不改变单调性
                    t--;
                deq[t]=j;
                deqv[t]=val;
                t++;
                //利用队头求出dp
                dp[j*w[i]+a]=deqv[s]+j*v[i];
                if(deq[s]==j-m[i])s++;//检查过期
            }
        }
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152966.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • JVM相关问题整理

    备注:针对基本问题做一些基本的总结,不是详细解答!1.运行时数据区域(内存模型)(必考)2.垃圾回收机制(必考)3.垃圾回收算法(必考)4.MinorGC和FullGC触发条件5.GC中Stoptheworld(STW)6.各垃圾回收器的特点及区别,怎么做选择?7.双亲委派模型8.JDBC和双亲委派模型关系9.JVM锁优化和锁膨胀过程10.JVM中G…

  • git 修改用户名以及邮箱_注册github账号

    git 修改用户名以及邮箱_注册github账号1、查看命令gitconfig–local–list2、查看当前用户名gitconfiguser.name3、查看邮箱gitconfiguser.email4、修改用户名gitconfiguser.namexxx5、修改邮箱gitconfiguser.emailxxx

  • 写一段代码在遍历 ArrayList 时移除一个元素?

    写一段代码在遍历 ArrayList 时移除一个元素?今天楼主继续分享一道经典Java面试题并进行相关知识点的拓展: 上题:写一段代码在遍历ArrayList时移除一个元素?该问题的关键在于面试者使用的是ArrayList的remove()还是Iterator的remove()方法。是使用正确的方式来实现在遍历的过程中移除元素,而不会出现ConcurrentModificationException异常的示例代码。…

  • 3dslicer使用教程_c4d视图设置

    3dslicer使用教程_c4d视图设置一、3DViewer视图窗口控制                                    视角控制左边一块可以控制当前3Dviewer窗口中显示的图像的视角,共有8个方向视角,左L(Left)、右R(Right)、前 A(Anterior)、后 P(Posterior)、上S(Superior)、下I(Interior)。点击后可以将视角切换到对应的方向。置中将3D视图放…

    2022年10月23日
  • 【实习之T100开发】T100 基础架构、命名原则

    【实习之T100开发】T100 基础架构、命名原则T100设计器随时补充知识点!执行程序的方法T100基础架构基本环境变量基本执行Shell一些作业编号记录随时补充知识点!sz文件名即可从Linux服务器下载文件到本机。。以a开头的是标准模组,以c开头的是客制模组。执行程序的方法假设你现在已经通过Xshell或某种工具连上公司的Linux服务器方法一:在Xshell命令行:r.r作业单号即可例如:r,raimi100方法二:利用menu指令调出T100系统首页,这个界面又有两种方法执行程序①

  • python如何安装matplotlib.pyplot_matplotlib中文

    python如何安装matplotlib.pyplot_matplotlib中文首先,一些博文上说可以在pycharm自动安装,也就是:File–Setting–ProjectInterpreter–±-输入指定模块安装,这对于社区版或教育版真的不行,好吗。安装的思路比较靠谱的,也是自己安装成功的方法。第一步:在官网上下载指定安装包:官网模块包:https://pypi.org/project需要什么模块就下载啥,需要注意的是与你的python版本一致(至于怎么一致,可以…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号