背包系列第一讲之01背包

2020-11-16 本文已影响0人 ITsCLG

学习动态规划的时候，我们看到大部分的书本都会提及“背包问题”，网络上相关的解释也很多。接下来小编将陆陆续续分享几种经典的背包类型及其算法设计。今天小编先来谈谈第一种，也就是“01背包问题”。这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。当然这里小编也是直接从网上搬了一个讲解的文章过来，讲的非常好，小编这里也要向这位大神致以崇高的敬意，然后小编自己再做个补充。

一、盗，如何有“道”

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

可偷窃物品

为了让偷窃的商品价值最高，你该选择哪些商品？要使用哪种途径呢？

二、简单算法

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

穷举

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

三、贪心算法

简单的算法既然执行效率这么低，我们当然想着来使用其它方法。相信大多数人都想拿优先拿价值大的物品，或者是性价比高的物品，但是我们很容易构思出反例。举个例子，这些物品中价值最大的就是音响，价值3000美元。好了，假设小偷现在拿了这个物品，会发现背包已经被装满，拿不了其它东西。然而作为一个聪明的小偷，想一想都知道这不是最优的做法。

有没有想过为什么贪心算法不可行？其实很简单，因为我们没办法确定背包什么状态是完美的。虽然我们知道背包的容量是4磅，但是我们并不知道最优的情况下我们能装多少，最优的结束状态是什么。我们把容量c看成了一个状态来进行贪心，贪心得到的结果是最优的，但是只是贪心能达到的状态的最优解，并不是全局的最优解，因为背包容量的限制，很有可能我们贪心策略下无法达到真正最优的状态。

用刚才的例子解释一下上面这段话，在贪心算法下，我们会选取容量是4磅，价值是3000美元的音响，这个物品拿取了之后背包的状态是4，获取的价值是3000。这个状态是贪心能够达到的最终状态，对于这个状态而言，它是最优解，但是这个状态并不是整体最优的情况。

理解了这个问题之后，再去推导解法就顺其自然了。贪心策略可以获取一些状态最优的情况，那么我们能不能记录下所有状态能够达到的最优的情况，最后在这些最优的情况当中选取一个最优的，它不就是整体最优解了吗？

四、动态规划

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

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

子问题

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

背包问题的网格如下：

所有网格

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

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

1.吉他行

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

吉他行01

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

第一个单元格表示背包的的容量为1磅。吉他的重量也是1磅，这意味着它能装入背包！因此这个单元格包含吉他，价值为1500美元。

下面来填充网格：

吉他行02

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

来看下一个单元格。这个单元格表示背包容量为2磅，完全能够装下吉他！

吉他行03

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

吉他行04

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

吉他行05

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

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

2.音响行

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

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

音响行01

该不该偷音响呢？

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

音响行02

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

音响行03

背包容量为4磅呢？终于能够装下音响了！原来最大价值为1500美元，但如果在背包中装入音响而不是吉他，价值将为3000美元！因此还是偷音响吧。

音响行04

你更新了最大价值。如果背包的容量为4磅，就能装入价值至少3000美元的商品。在这个网格中，你逐步地更新最大价值。

音响行05

3.笔记本电脑行

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

电脑行01-02

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

电脑行03

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

哪个价值高

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

比较

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

找最大值

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

价值VS

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

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

终表

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

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

状态转移方程

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

小偷盗取的最大价值

再增加一件商品将如何呢？

假设你发现还有第四件商品可偷，一个iPhone！（或许你会毫不犹豫的拿走，但是请别忘了问题的本身是要拿走价值最大的商品）

手机

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

添加前的终表

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

添加iphone行

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

iphone行01

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

iphone行02

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

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

取最大价值

3磅容量的最大价值为2000美元！再加上iPhone价值2000美元，总价值为4000美元。新的最大价值诞生了。

最终的网格如下：

新的终表

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

图

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

五、算法基本思路实现

在解决问题之前，为描述方便，首先定义一些变量与数据结构：

（1）物品个数n

（2）背包容量c

（3）V[i]表示第 i个物品的价值

（4）W[i]表示第 i个物品的重量

（5）F[i][c]表示前i件物品恰放入一个容量为c的背包可以获得的最大价值。

利用子问题定义状态，该问题的状态转移方程便是：F[i][c] = max{F[i−1][c],F[i−1][c –W[i]]+ V[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为c的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i−1件物品相关的问题。如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为c的背包中”，价值为F[i−1][c]；如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为c−W[i]的背包中”，此时能获得的最大价值就是F[i−1][c−W[i]]再加上通过放入第i件物品获得的价值V[i]。

C++代码如下所示：

二维数组

运行截图：

运行结果

六、优化空间复杂度

以上方法的时间和空间复杂度均为O(n*c)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(c)。

我们先来观察状态转移方程：F[i][c] = max{F[i−1][c], F[i−1][c−W[i]]+ V[i]}

注意到这个二维数组的下一行的值，只用到了上一行的正上方和左边的值。因此可用滚动数组的思想，只要一行即可,也就是一维数组。我们可以看到，要想得到F[i][c]，我们需要知道F[i - 1][c] 和F[i - 1][c−W[i]]，由于我们使用二维数组保存中间状态，所以可以直接取出这两个状态。

依赖数据图

当我们使用一维数组存储状态时，F[c]表示，在执行i次循环后(此时已经处理i个物品)，前i个物体放到容量c时的最大价值，即之前的F[i][c]。与二维相比较，它把第一维隐去了，但是二者表达的含义还是相同的，只不过针对不同的i，F[c]一直在重复使用，所以，也会出现第i次循环可能会覆盖第i - 1次循环的结果。

状态转移方程：F[c] = max{F[c], F[c−W[i]] + V[i]}

为了求F[c],我们需要知道，前i - 1个物品放到容量c的背包中带来的收益，即之前的F[i - 1][c] 和前i - 1件物品放到容量为c - W[i]的背包中带来的收益，即之前的F[i - 1][c - W[i]] + V[i]。

难点：由于我们只使用一维数组存储，则在求这两个子问题时就没有直接取出那么方便了，因为，第i次循环可能会覆盖第i - 1次循环的结果。

现在我们来求这两个值

1）前i - 1个物品放到容量c的背包中带来的收益，即之前的F[i - 1][c] ：

由于，在执行在i次循环时，F[c]存储的是前i个物体放到容量c时的最大价值，在求前i个物体放到容量c时的最大价值(即之前的F[i][c])时，我们是正在执行第 i 次循环，F[c]的值还是在第i- 1 次循环时存下的值，在此时取出的F[c]就是前i - 1个物体放到容量c时的最大价值，即F[i - 1][c]。

2）前i - 1件物品放到容量为c - W[i]的背包中带来的收益，即之前的F[i - 1][c - W[i]] + V[i]。

由于，在执行第i次循环前，F[0~ c]中保存的是第i - 1次循环的结果，即是前i - 1个物体分别放到容量0 ~ c时的最大价值，即F[i - 1][0 ~ c]。

则在执行第i次循环前，F 数组中c - W[i]的位置存储就是我们要找的前i - 1件物品放到容量为c -W[i]的背包中带来的收益 (即之前的F[i - 1][c - W[i]])，这里假设物品是从数组下标1开始存储的。

注意一点，我们是由第 i - 1 次循环的两个状态推出第 i 个状态的，而且c > c - W[i]，则对于第i次循环，背包容量只有当c..0循环时，才会先处理背包容量为c的状况，后处理背包容量为c- W[i]的情况。

具体来说，由于，在执行c时，还没执行到c - W[i]的，因此，F[c - W[i]]保存的还是第i - 1次循环的结果。即在执行第i次循环且背包容量为c时，此时的F[c]存储的是F[i -1][c] ，此时F[c-W[i]]存储的是F[i - 1][c-W[i]]。

相反，如果在执行第 i 次循环时，背包容量按照0..c的顺序遍历一遍，来检测第 i 件物品是否能放。此时在执行第i次循环且背包容量为c时，此时的F[c]存储的是F[i - 1][c] ，但是，此时F[c-W[i]]存储的是F[i][c-W[i]]。

因为，c > c - weight[i]，第i次循环中，执行背包容量为c时，容量为c-W[i]的背包已经计算过，即F[c - W[i]]中存储的是F[i][c- W[i]]。即，对于01背包，按照增序枚举背包容量是不对的。

有点绕，我们先按照增序枚举的顺序来编写代码，C++代码截图如下：

增序

运行截图如下：

增序枚举运行截图

对比下我们之前正常的运行截图，可以发现解过从第一行第二列数据就开始出错。我们从代码可以很容易看出来。

我们出错的地方是在第一行第二列数据，正常的值应该为1500，这里变成了3000。我们来分析下这个过程。

我们在进行第一次计算时，有F[1]=max{F[1],F[1-w[1]]+v[1]}=max{F[1],F[0]+v[1]}=max{F[1],F[0]+1500}；注意，这里的max里的F[1]和F[0]指的是上一行的数据，相当于二维数组的F[0][1]和F[0][0]。边界值都设置为0，因此这里的F[1]=F[0]=0；外部的F[1]相当于二维数组的F[1][1]，特别关注这个地方。可以得到F[1]=max{0,0+1500}=1500。

我们在进行第二次计算时，有F[2]=max{F[2],F[2-w[1]]+v[1]}=max{F[2],F[1]+v[1]}=max{F[2],F[1]+1500}；注意，正常情况下，这里的max里的F[2]和F[1]指的是上一行的数据，相当于二维数组的F[0][2]和F[0][1]，都是边界值故都为0。也就是说正常情况下F[2]=F[1]=0；但是这时侯我们会发现，我们上一次计算时已经重新对F[1]赋值为1500，这里的F[1]存储的是使用二维数组时F[1][1]的值，我们要的是F[0][1]这个值来参与运算，所以当然会得到错误的计算结果。

按照这样的分析，可以得到我们上述图片展示的错误的运行结果。因此增序枚举是错误的。

正确的代码截图如下：

滚动一维数组逆序枚举

使用一维数组F[c]存储中间状态，维表示背包容量。初始化时，除了F[0] = 0，其他全为负无穷。原因：只有容量为0 的背包可以什么物品都不装就能装满，此时价值为0。其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为负无穷了【当然小编的代码并没有去设置，严谨点来说确该如此去做】。

运行截图如下：

正确的运行结果

七、初始化的细节问题

求最优解的背包问题时，有两种问法：

（1）在不超过背包容量的情况下，最多能获得多少价值

（2）在恰好装满背包的情况下，最多能获得多少价值

主要的区别为是否要求恰好装满背包。但这两种问法的实现方法是在初始化的时候有所不同。

恰好装满背包的情况：

代码设计时，我们使用二维数组F[i][c]存储中间状态，其中第一维表示物品，第二维表示背包容量。初始化时，F[i][0] = 0（第一列）。初始化 F数组就是表示：在没有任何物品可以放入背包时的合法状态。对于恰好装满背包，只有背包容量为 0（第一列），可以什么物品都不装就能装满，这种情况是合法情况，此时价值为0。其他f[0][c]（第一列）是都不能装满的，此时有容量没物品。而其他位置（除去第一行和第一列的位置），我们为了在计算中比较最大值，也要初始化为负无穷。我们从程序的角度上看，我们只允许装入背包物品的序列的起始位置是从第一列开始，这些起始位置都是合法位置，且能恰好装满的情况收益均为正值，到F[n][c]终止。

注意，我们虽然是求恰好装满，还是需要枚举所有可以装入背包的物品，只要能装入，还需装入，收益有增加。只不过，由于恰好装满的物品的序列肯定是从第一列某行开始的，且之后的收益肯定是正值。对于非恰好装满的物品序列，其实位置肯定是从第一行某位置开始的，由于此时被初始化为负无穷，在和那些恰好装满物品序列带来的价值时，肯定是小的。所以，我们最后能获得最大值。

C++代码如下：