参考文献：算法图、动态规划

动态规划是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题。

背包问题

假设你是一个xfdgb，背包可以装4公斤的东西。你可以偷三样东西。

为了得到最高价值的赃物，你应该选择哪些物品？

简单算法最简单的算法如下：尝试所有可能的商品组合，找到价值最高的组合。

这是可行的，但是速度很慢。在3个项目的情况下，你需要计算8个不同的集合；当有4个项目时，你需要计算16套。每增加一件商品，需要计算的收藏数量就会翻倍！这个算法的运行时间是O(2n)，真的慢如蜗牛。

2.动态规划

对于背包问题，要先解决小背包(子背包)的问题，再逐步解决甜鹅的问题。

每个动态规划算法都是从一个网格开始的，背包问题的网格如下。

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

网格最初是空的。你将填写每个单元格，网格填好后，你会找到问题的答案！你必须效仿。请创建一个网格，我们将一起填充它。

计算此网格中单元格值的公式将列在吉他行之后。让我们一步一步来。让我们看看第一行。

这是吉他线，也就是说你会试着把吉他装进背包。在每个牢房里，你需要做一个简单的决定：你想偷吉他吗？别忘了，你得找一批价值最高的商品。

第一个单元格表示背包的容量为1磅。这把吉他也有1磅重，这意味着它可以装进背包里！所以这个单元包含吉他，价值1500美元。

让我们开始填充网格。

像这个单元一样，每个单元将包含当前可以放入背包的所有项目。

看看下一个牢房。这个单元格表示背包容量2磅，完全可以装下吉他！

该行中的其他单元格也是如此。别忘了，这是第一行，只有吉他是供你选择的。换句话说，你假装你还不能偷另外两种商品。

这时，你可能在想：甜鹅的问题指的是一个4磅重的背包。为什么要考虑容量为1磅或2磅的背包？我前面说过，动态规划从小问题开始，逐步解决大问题。这里解决的子问题会帮你解决大问题。请继续读下去，你以后会明白的。

网格应该是这样的。

别忘了，你要做的就是让背包里的物品价值最大化。这条线代表当前最大值。它指出，如果你有一个容量为4磅的背包，里面能装的货物的最大价值是1500美元。

88b68148289f4ce784f7df000c?from=pc">

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

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美元。新的最大价值诞生了！

最终的网格如下。

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

请找出这个问题的答案，再接着往下读。

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

练习

假设你还可偷另外一件商品——MP3播放器，它重1磅，价值1000美元。你要偷吗？

行的排列顺序发生变化时结果将如何

答案会随之变化吗？假设你按如下顺序填充各行：音响、笔记本电脑、吉他。网格将会是什么样的？请自己动手填充这个网格，再接着往下读。

网格将类似于下面这样。

答案没有变化。也就是说，各行的排列顺序无关紧要。