Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说01背包算法图解_01背包问题例题讲解[通俗易懂],希望能够帮助你!!!。

假设你是一个小偷，背着一个可装下 4 磅东西的背包，你可以偷窃的物品如下：

为了让偷窃的商品价值最高，你该选择哪些商品？

简单算法

最简单的算法是：尝试各种可能的商品组合，并找出价值最高的组合。

这样显然是可行的，但是速度非常慢。在只有 3 件商品的情况下，你需要计算 8 个不同的集合；当有 4 件商品的时候，你需要计算 16 个不同的集合。每增加一件商品，需要计算的集合数都将翻倍！这种算法的运行时间是 O(2ⁿ)，真的是慢如蜗牛。

动态规划

解决这样问题的答案就是使用动态规划！下面来看看动态规划的工作原理。动态规划先解决子问题，再逐步解决大问题。

对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。

比较有趣的一句话是：每个动态规划都从一个网格开始。

背包问题的网格如下：

网格的各行为商品，各列为不同容量（1~4 磅）的背包。所有这些列你都需要，因为它们将帮助你计算子背包的价值。

网格最初是空的。你将填充其中的每个单元格，网格填满后，就找到了问题的答案！

1. 吉他行

后面会列出计算这个网格中单元格值得公式，但现在我们先来一步一步做。首先来看第一行。

这是吉他行，意味着你将尝试将吉他装入背包。在每个单元格，都需要做一个简单的决定：偷不偷吉他？别忘了，你要找出一个价值最高的商品集合。

第一个单元格表示背包的的容量为 1 磅。吉他的重量也是 1 磅，这意味着它能装入背包！如果不装它，总价值为0；如果装了它，总价值就是1500了！因此为使总价值最大，应装入吉他。这个单元格应包含吉他，价值为 1500 美元。

下面来填充网格。

与这个单元格一样，每个单元格都将包含当前可装入背包的所有商品。

来看下一个单元格。这个单元格表示背包容量为 2 磅，完全能够装下吉他！同样，如果不装它，总价值是0；如果装入吉他，总价值就是1500。为了在当前条件下获得最大总价值，那肯定得装呀！

这行的其他单元格也一样。别忘了，这是第一行，只有吉他可供你选择，换而言之，你假装现在还没发偷窃其他两件商品。

此时你很可能心存疑惑：原来的问题说的额是 4 磅的背包，我们为何要考虑容量为 1 磅、2 磅等得背包呢？前面说过，动态规划从小问题着手，逐步解决大问题。 解决的子问题将帮助你解决大问题。

别忘了，你要做的是让背包中商品的价值最大。这行表示的是当前的最大价值。它指出，如果你有一个容量 4 磅的背包，且只有吉他可供选择，可在其中装入的商品的最大价值为 1500 美元。

你知道这不是最终解。随着算法往下执行，你将逐步修改最大价值。

2. 音响行

我们来填充下一行——音响行。你现在处于第二行，可以偷窃的商品有吉他和音响。

我们先来看第一个单元格，它表示容量为 1 磅的背包。在此之前，可装入 1 磅背包的商品最大价值为 1500 美元。

该不该偷音响呢？

背包的容量为 1 磅，显然不能装下音响。由于容量为 1 磅的背包装不下音响，因此最大价值依然是 1500 美元。

接下来的两个单元格的情况与此相同。在这些单元格中，背包的容量分别为 2 磅和 3 磅，而以前的最大价值为 1500 美元。由于这些背包装不下音响，因此最大的价值保持不变。

背包容量为 4 磅呢？终于能够装下音响了！那要不要装音响呢？
在枚举到上一件物品——吉他 时，我们已经得出的最大价值为 1500 美元，但如果在背包中装入音响而不是吉他，价值将为 3000 美元！因此还是偷音响吧。

你更新了最大价值。如果背包的容量为 4 磅，就能装入价值至少 3000 美元的商品。

3. 笔记本电脑行

下面以同样的方式处理笔记本电脑。笔记本电脑重 3 磅，没法将其装入 1 磅或者 2 磅的背包，因此前两个单元格的最大价值仍然是 1500 美元。

对于容量为 3 磅的背包，可以装下电脑了，那么该如何抉择呢？
原来的最大价值为 1500 美元，但现在你可以选择偷窃价值 2000 美元的笔记本电脑而不是吉他，这样新的最大价值将为 2000 美元。

对于容量为 4 磅的背包，情况很有趣。 当前的最大价值为 3000 美元，你可不偷音响，而偷笔记本电脑，但它只值 2000 美元。

价值没有原来高，但是等一等，笔记本电脑的重量只有 3 磅，背包还有 1 磅的重量没用！

在 1 磅的容量中，可装入的商品的最大价值是多少呢？你之前已经计算过了！

根据之前计算的最大价值可知，在 1 磅的容量中可装入吉他，价值 1500 美元。因此，你需要做如下的比较：

你可能始终心存疑惑：为何要一步步计算小背包可装入的商品的最大价值呢？但愿你现在明白了其中的原因！余下了空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品。
笔记本电脑和吉他的总价值为 3500 美元，因此偷它们是更好的选择。

最终的网格类似于下面这样。

答案如下：将吉他和笔记本电脑装入背包时价值更高，为 3500 美元。

你可能认为，计算最后一个单元格的价值时，我们使用了不同的公式。那是因为填充之前的单元格时，我们故意避开了一些复杂的因素。其实，计算每个单元格的价值时，使用的公式都相同。这个公式如下。

你可以使用这个公式来计算每个单元格的价值，最终的网格将与前一个网格相同。现在你明白了为何要求解子问题了吧？你可以合并两个子问题的解来得到更大问题的解。

再增加一件商品将如何呢

假设你发现还有第四件商品可偷——一个 iPhone！

此时需要重新执行前面所做的计算吗？不需要。别忘了，动态规划逐步计算最大价值。到目前为止，计算出的最大价值如下：

这意味着背包容量为 4 磅时，你最多可偷价值 3500 美元的商品。但这是以前的情况，下面再添加表示 iPhone 的行。

我们还是从第一个单元格开始。iPhone 可装入容量为 1 磅的背包。之前的最大价值为 1500 美元，但 iPhone 价值 2000 美元，因此该偷 iPhone 而不是吉他。

在下一个单元格中，你可装入 iPhone 和吉他。

对于第三个单元格，也没有比装入 iPhone 和吉他更好的选择了。

对于最后一个单元格，情况比较有趣。当前的最大价值为 3500 美元，但你可以偷 iPhone，这将余下 3 磅的容量。

之前已经计算过了，3 磅容量的最大价值为 2000 美元！ 再加上 iPhone 价值 2000 美元，总价值为 4000 美元。新的最大价值诞生了！

最终的网格如下。

问题：沿着一列往下走，最大价值可能降低吗？

答案是：不可能。因为每次迭代时，你都存储的是当前的最大价值。最大价值不可能比以前低！

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。