初步了解01背包问题(分治篇)

Kubrnete 等级 458 0 0

目录

问题描述

输入格式

输出格式

基于0/1背包的迭代算法

0/1背包问题的分析

分治法

总结


问题描述

Coda非常喜欢玩“NewWorld Online”,受到某部动画的影响,他决定创建名为“梅普露”的角色,并把所有技能点都加到防御力上。Coda发现了一个包含了n行数据的列表,表上每行有一组数据,包含两个整数aibi,决定了第i 次点技能时消耗ai 点技能点,提升bi 点属性值。

Coda在加点时可以从列表中选择喜欢的一组数据作为加点时的消耗和提升,但是每组数据使用过一次就不能再次使用了。

Coda现在拥有p个技能点,初始防御力为d,请问如果Coda把这些技能点全拿来加防御力,最高能到达多少防御力?

输入格式

第一行包含3个整数: n,p,d,分别表示列表中数据组数、拥有的技能点数和初始防御力。 接下来n行,每行包含2个整数aibi,分别表示列表中各组数据,ai 是加点时技能点的消耗,bi 是加点时防御力的提升。

输出格式

一行,包含一个整数,最大可以达到的防御力。

初步了解01背包问题(分治篇))初步了解01背包问题(分治篇)

(如果想要直接看动态规划部分,请直接点击动态规划篇前往下一篇文章)


这是一个经典的【01背包】问题:

有N个物品,它们有各自的体积wi 和价值vi,现有给定容量C的背包,如何让背包里装入的物品具有最大的价值总和?

贪心的尝试

上一篇文章中,我们提到一种直接选择当前最优解的贪心算法。现在,让我们开启贪婪模式——既要装得多,又要价值高,那么就选性价比最高的好了——按照物品单价从大到小来装。 这可行吗?

在重量相同的情况下,我们总会选择对价值贡献最大的物品。然而,我们并不能确定这个贪心策略能否把背包装满。

我们只是按照了单价更高的策略依次对物品作选择。但物品不可分割。因此这个贪心策略只是解决了部分背包问题,在这里不能成立。我们很容易能够给出反例,当所有的物品单价相同,又或者:

N=3,C=30

物品:A B C

重量:20 15 15

价值:30 20 20

让我们理解一下贪心算法的适用情况:

  1. 因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留,并且,每一步的最优解一定包含上一步的最优解。在贪心算法中,作出的每步贪心决策都无法改变。
  2. 所谓贪心选择性质,是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。换句话说,当考虑做何种选择的时候,我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。
  3. 对于一个具体问题,要确定它是否具有贪心选择性质,每一步的最优解一定包含上一步的最优解。则必须证明每一步所作的贪心选择最终导致问题的整体最优解。

这可咋办呢?贪心用不了,dp又不会,只能用暴力天天TLE才能水水题这样子。

基于01背包的迭代算法

01背包问题的分析

01背包问题,顾名思义,是0/1的规划问题。由于物品不可分割且只能拿一次,于是对于每个物品只有两个选择:盘它或者不盘。

我们将选记为1,不选记为0。盘还是不盘?这是个问题。

下面我们以本题的输入样例作为例子(始值改为3 3 0):

初步了解01背包问题(分治篇))初步了解01背包问题(分治篇)

假定背包容量c=3,物品数n=3,它们的价值(v)和重量(w)如上图。现在要从中选择物品装入背包中,要求物品的重量不能超过背包的容量,并且最后放在背包中物品的总价值最大。

对于物品1,背包的当前容量为3>1,因此有两种选择。当我们选择一个物品的时候,背包的容量会减少,但是里面的物品总价值会增加。就像下面这样:

初步了解01背包问题(分治篇))初步了解01背包问题(分治篇)

这样就分出了两种情况,我们继续进行选择。如果我们选择了物品1,那么对于物品2,当前剩余容量为2,也可以选或者不选。可见,我们每次对物品做出一次选择,上面的一种可能就会分裂成两种。让我们继续画下去,最终就会形成我们的决策树。

初步了解01背包问题(分治篇))初步了解01背包问题(分治篇)

最后,我们在这棵决策树上(每个被圈中的方框都是待选的结果)通过比较得到最大值5。

(注:图中本应有9个待选结果,由于有四个容量不足,无法继续分裂更多可能)

值得说明的是,通常在问题中会更有更多复杂的用例,建议读者可以仿着画一次图,以便理解。

分治法

接下来,我们将问题扩展到一般情况。为了实现这个目的,我们需要将问题进行抽象并建模,然后将其划分为更小的子问题,找出递推关系式。

  1. 问题抽象:我们对第 i 个物品的选择定义为 xi(选为1,不选为0),vi代表第i个珠宝的价值,wi代表第i个珠宝的重量。
  2. 约束条件:x1w1 + x2w2 + x3w3 + ... + xnwn < c。对于上面的例子,则为1x1+2x2+3*x3<=3
  3. 建模:题目要求找出x1v1 + x2v2 + x3v3 + ... + xnvn 中的最大值
  4. 定义函数:V_total(i,j):表示当前背包剩余容量为j 时,前i 个物品最佳组合所对应的价值。

需要可以说明的是:原问题是要求出【**将n件物品放入容量为c的背包的最优价值】;**

现在,我们来考虑一下子问题:

我们将前*i* 件物品放入容量为*j* 的背包,所得到的最优价值为V_total(i,j)。如果只考虑第i件物品放还是不放,那么就可以转化为一个只涉及到前i-1个物品的问题

如果不选第i个物品,那么问题就转化为“前i-1\件物品放入容量为j的背包中的最优价值组合”,对应的值为V_total(i-1,j)。如果放第i个物品,那么问题就转化成了“前i-1件物品放入容量为j-wi的背包中的最优价值组合”,对应的值为V_total(i-1,j-wi)+vi

为避免看不懂,这里再次放出这张决策图。(建议自己另画一张进行分析)。

初步了解01背包问题(分治篇))初步了解01背包问题(分治篇)

怎么判断一个物品选还是不选呢?经过了上述分析,我们知道对于第i 个物品,我们有以下两种情况:

  • ①若背包剩余容量不足以容纳这个物品,则背包的价值与前i-1个物品的价值相同,即V_total(i,j) = V_total(i-1,j)
  • ②若背包剩余容量足以装下物品,则判断选或者不选背包中物品价值的大小,选出较大的一个。

​ 即Max{V_total(i-1,j-wi) + vi, V_total(i-1,j)}

于是有如下的递推关系:

初步了解01背包问题(分治篇))初步了解01背包问题(分治篇)

现在,我们可以照着这个递推关系,从i=n,j=c开始,写出递归解法的关键部分:

int V_total(int i,int j){//通过递归找出最优的组合
    if(j<w[i])
        return V_total(i - 1, j);
    else
        return max(V_total(i - 1, j), V_total(i - 1, j - w[i]) + v[i]);

}

初步了解01背包问题(分治篇)

没想到吧,竟然如此简单?(完整代码还要判断一下n==0或c==0的情况,由于重点不在这,就不附代码了)

总结

我们通过将大问题拆分成小问题,并寻找问题中的递推关系,解决一个个小问题,最终成功解决原问题。但由于分治法在子问题和子子...问题过程中进行了多次的重复计算(尝试每个组合的方法的问题是重复步骤,因为它存在重叠的子问题)如下图:

初步了解01背包问题(分治篇))初步了解01背包问题(分治篇)

因此这种方法具有重复的计算和时间复杂性是指数的。(指数级别是由树的深度depth决定的)

为了找到更好的解决方案,我们将在下一篇文章中学习动态规划算法。动态规划具有记忆性,一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间。它试图仅对每个子问题解决一次,从而减少计算量。(所以在问题满足最优性原理(见下文)之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。)这种做法在重复子问题的数目关于输入的规模呈指数增速时特别有用。

下面进入正题,请看下一篇文章:基于01背包问题的动态规划算法

本文转自 https://blog.csdn.net/guanguandaren/article/details/107940122,如有侵权,请联系删除。

收藏
评论区

相关推荐

linux基础命令1
language date date %Y/%m/%d date %H:%M:%S cal cal 2021 cal 01 cal 01 2021 cal 1 2021 bc scale3 quit tab tab tab ctrl c ctrl d shift pageUp shift p
.NET C#到Java没那么难,DB篇
.NET C到Java没那么难,DB篇 .NET C到Java没那么难,DB篇 前言 .NET C到Java没那么难,都是面向对象的语言,而且语法还是相似的,先对比一下开发环境,再到Servlet,再到
.NET C#到Java没那么难,MVC篇
.NET C到Java没那么难,MVC篇 .NET C到Java没那么难,MVC篇 最典型的JAVA MVC就是JSP servlet javabean的模式。比较好的MVC,老牌的有Struts、
.NET C#到Java没那么难,Servlet篇
.NET C到Java没那么难,Servlet篇 .NET C到Java没那么难,Servlet篇 前言 .NET C到Java没那么难,都是面向对象的语言,而且语法还是相似的,先对比一下开发
Go Iris学习笔记01
Iris MVC支持 文档: 支持所有 HTTP 方法, 例如,如果想要写一个 GET 那么在控制器中也要写一个 Get() 函数,你可以在一个控制器内定义多个函数。 每个控制器通过 BeforeActivation 自定义事件回调,用来自定义控制器的结构的方法与自定义路径处理程序,如下:(还未实验) func (m
初步了解01背包问题(分治篇)
目录 问题描述(问题描述) 输入格式(输入格式) 输出格式(输出格式) 基于0/1背包的迭代算法(基于01背包的动态规划算法) 0/1背包问题的分析(01背包问题的分析) 分治法(分治法) 总结(总结) 问题描述 Coda非常喜欢玩“NewWorld Online”,受到某部动画的影响,他
问题 first path segment in URL cannot contain colon 的解决方案
目录问题解决 问题使用Golang开发流媒体服务器处理Post请求时,遇到了这个报错信息:2020/12/14 07:21:01 callback post failed2020/12/14 07:21:01 error::8080/api/callback: first path segment in URL cannot contain col
完全背包问题
问题描述 有n种物品和一个容量为c的背包,每种物品都就可以选择任意多个,第i种物品的价值为v\i\,体积为w\i\,求解:在不超过背包容量的情况下,选择放入哪些物品能够使得背包中的价值最大?跟01背包一样,完全背包也是一个很经典的动态规划问题,不同的地方在于01背包问题中,每件物品最多选择一件;而在完全背包问题中,只要背包装得下,每件物品可
python刷题-01字串
问题描述对于长度为5位的一个01串,每一位都可能是0或1,一共有32种可能。它们的前几个是:0000000001000100001100100请按从小到大的顺序输出这32种01串。 输出格式输出32行,按从小到大的顺序每行一个长度为5的01串。 样例输出00000000010001000011<以下部分省略 for i in range(0
软件设计模式概述
01 软件设计模式概述 01 软件设计模式概述 软件设计模式的产生背景 "设计模式"这个术语最初并不是出现在软件设计中,而是被用于建筑领域的设计中。 1977 年,美国著名建筑大师、加利福尼亚大学伯克利分校环境结构中心
SQL笔试 I 经典44题及答案解析~
↑ 关注 + 星标  有趣的不像个技术号每晚九点,我们准时相约   今天这篇文章,是关于44道经典SQL测试题: 01 建表语句 create table Student(sid varchar(10),sname varchar(10),sage datetime,ssex nvarchar(10));insert into Stude
题解5道c++面试题第一期(含解题思路、答案解析和实现代码)
本篇文章送上5道c/c++面试题目,并附上答案、解题思路以及扩展知识。 1. 求下面函数的返回值c++include <stdio.hint func(int x) int iCnt 0; while(x) iCnt++; x x&(x1); return iCnt;int main() printf("cnt %d\n", func(9999
手写strcpy和memcpy代码实现
本篇文章聊一下strcpy和memcpy的代码实现,这两个也是c和c++面试中常考的问题点。 1. 手写strcpy首先看一下,一份标准的strcpy的实现如下:cchar strcpy(char strDest, const char strSrc) assert( (strDest ! NULL) && (strSrc ! NULL)); char ad
面试官嘲笑我,这你都不会?
01 背景大家好,我是阿沐!你的收获便是我的喜欢,你的点赞便是对我的认可。多年前刚毕业出来工作的时候,那个时候刚毕业对缓存的使用基本上可以说很少涉及,在大学做课件设计或者小型项目也都是用不到缓存,再者说了我大学是做嵌入式写汇编语言和c语言的。当时出实习去找工作并不顺利,面试官问了知道redis和memcached区别嘛?额,我当时虽然也做了一些功课,就是恶补
Python爬虫 | Selenium爬取当当畅销图书排行
01 前言 上篇文章我们爬取了,心情相当愉悦,今天这篇文章我们使用Selenium来爬取当当网的畅销图书排行。正所谓书中自有黄金屋,书中自有颜如玉,我们通过读书学习来提高自身的才华,自然能有荣华富贵,也自然少不了漂亮小姐姐。 02 准备工作 在爬取数据前,我们需要安装Selenium库以及Chrome浏览器,并配置好Chro