大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
看了很多网上的博客,发现对于0-1背包问题很多讲的都很专业,初学者学起来还是比较吃力,今天我就用最简单最形象的语言来描述一下0-1背包问题,为什么不能用贪婪算法,而要选择使用动态规划。
- 首先对于0-1背包问题,我们需要知道的是:每一个物品只有1个,要么全拿,要么不拿,最后使得拿到的物品的总价值最大。
- 假如一个小偷有一个可以容纳4千克的背包,但是发现面前只有有3样物品可以偷:台灯(30元,4千克)、音响(20元,3千克)、充电宝(15元,1千克)(价格和重量可能有点奇怪?)。问,小偷能够偷到的物品的最大价格是多少(物品的重量不得超过背包的重量)?
贪婪算法(不适用!!!)
- 如果我们使用贪婪算法,每次都拿最贵的物品,那么我们可以看到:一开始拿到的是最贵的台灯,但是此时小偷已经拿到了4千克的重量,刚好把背包填充满了,无法再去偷第二个物品,那么此时获得的最大价值就是30元。但是我们发现如果偷音响和充电宝,可以获得的最大价值就是35元,明显比投台灯获得价值大。 所以贪婪算法在这里是不适用的!
动态规划
- 动态规划的问题,一般是先解决子问题,然后由子问题推导,逐步解决大问题,所以我们可以先解决1千克的背包能够获得的最大价值,2千克的背包能够获得的最大价值,直到4千克的背包能够获得的最大价值。首先我们先搞定状态以及转移方程。我们这里定义状态f[i][v],表示前i件物品恰好放入一个容量为v的背包可以获得的最大价值。仔细想一下,我现在获得的最大价值可以建立在第 i 个物品我不偷,那重量是v;也可以是第 i 个物品我偷了,那么前 i-1 个物品的总重量是 v-c[i] ,再加上我现在准备偷的第 i 个物品的价值 v[i],取两者的最大值即可。那么,转移方程就是: f [ i [ [ v ] = m a x ( f [ i − 1 ] [ v ] , f [ i − 1 ] [ v − c [ i ] ] + v [ i ] ) f[i[[v] = max(f[i-1][v],f[i-1][v-c[i]]+v[i]) f[i[[v]=max(f[i−1][v],f[i−1][v−c[i]]+v[i])
- 听起来挺抽象的,接下来我们可以用一个网格来描述(每一个单元格都包含当前可装入背包的所有物品):
- 然后我们开始遍历这个网格,一开始我们填充台灯这一行。发现,当背包的容量为1千克的时候,由于台灯的重量是4千克,所以偷不了,所以此时获得的最大价值为0元。
直到背包的容量为4千克的时候,我们才可以偷台灯,此时获得的最大价值为30元。
- 接下来我们开始遍历音响这一行,现在可以偷的物品有台灯和音响(每一行可以偷的物品只有当前行以及前一行的物品),同样的,发现直到背包的容量是3千克的时候才能装的下音响。
当背包的重量是4千克的时候,我们要么只能偷台灯,要么只能偷音响,发现偷台灯的价值会更大一点,所以我们选择偷台灯。 - 最后我们来遍历充电宝这一行,发现当背包重量为1千克和2千克的时候,我们只能容纳充电宝,所以获得的最大价值为15元。
当背包容量为3千克时候,我们可以获得的最大价值就是偷了音响,20元。
当背包容量为4千克的时候,我们可以不偷充电宝,那么直接由上一行获得的最大价值传递过来,就是30元;我们也可以偷充电宝,那么要偷充电宝的话就只剩下3千克的背包容量了,在3千克的背包容量时能够获得的最大价值是20元,所以最后获得的最大价值为35元。两种情况比较,取最大值,所以最后小偷获得的最大价值为35元。 - 对于这个0-1背包问题,如果我们再增加一件物品,可以继续如此推导下去。如果我们偷的物品的顺序不一样(比如先偷音响,再偷台灯,再偷充电宝),也不会影响到最终的结果。
- 最后想说的是,如果小偷可以偷一个物品的某一部分,比如可以偷一袋米的一部分米,那么动态规划在这里就不适用了,反而可以用贪心算法实现。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164410.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...