彻底搞懂0-1背包问题（动态规划）

全栈程序员-站长 • 2022年7月26日上午9:00 • 未分类 • 阅读 9

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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])$
听起来挺抽象的，接下来我们可以用一个网格来描述（每一个单元格都包含当前可装入背包的所有物品）：

然后我们开始遍历这个网格，一开始我们填充台灯这一行。发现，当背包的容量为1千克的时候，由于台灯的重量是4千克，所以偷不了，所以此时获得的最大价值为0元。

直到背包的容量为4千克的时候，我们才可以偷台灯，此时获得的最大价值为30元。
接下来我们开始遍历音响这一行，现在可以偷的物品有台灯和音响（每一行可以偷的物品只有当前行以及前一行的物品），同样的，发现直到背包的容量是3千克的时候才能装的下音响。
当背包的重量是4千克的时候，我们要么只能偷台灯，要么只能偷音响，发现偷台灯的价值会更大一点，所以我们选择偷台灯。
最后我们来遍历充电宝这一行，发现当背包重量为1千克和2千克的时候，我们只能容纳充电宝，所以获得的最大价值为15元。
当背包容量为3千克时候，我们可以获得的最大价值就是偷了音响，20元。
当背包容量为4千克的时候，我们可以不偷充电宝，那么直接由上一行获得的最大价值传递过来，就是30元；我们也可以偷充电宝，那么要偷充电宝的话就只剩下3千克的背包容量了，在3千克的背包容量时能够获得的最大价值是20元，所以最后获得的最大价值为35元。两种情况比较，取最大值，所以最后小偷获得的最大价值为35元。
对于这个0-1背包问题，如果我们再增加一件物品，可以继续如此推导下去。如果我们偷的物品的顺序不一样（比如先偷音响，再偷台灯，再偷充电宝），也不会影响到最终的结果。