背包九讲

背包问题是动态规划问题中最为经典的问题之一，可以说完全弄明白了背包问题，能够很大程度上帮助我们了解动态规划转移方程的基本推导。背包问题的经典讲义为浙江大学崔添翼同学撰写的《背包九讲》，本文是我阅读该文章过程中的笔记和感想。

动态规划的思路其实并不难想到，大多数问题只需要看一眼就能知道是否可以采用动规求解了，难点在于如何推导出合适的状态矩阵和状态转移方程。这需要我们多手写DP表，仔细找规律。

动态规划问题基本概念

动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。

一般来说，当问题具有以下三个特点的时候，适用动态规划方法解决：

• 最优子结构： 大问题的最优解可以由小问题的最优解推出
• 无后效性： 如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。
• 重叠子问题：相同的子问题可能被重复求解多次 其实，上述前两个特点准确说是分治算法的特点。动态规划和递归算法本质上都是分治算法的一个子集，它们都是将大问题分解为小问题进行求解。而第三个特点区分了使用递归和使用动态规划的情况：一般来说，子问题独立的情况我们使用递归算法解决即可，而子问题重叠必须使用动态规划，否则时间复杂度会大大升高。

我们以最简单的斐波那契数列为例，当求解第101项时，我们需要计算第100项和第99项，而当求解第102项时，我们需要求解100项和第101项。如果我们直接使用递归算法，那么求解第101项和第102项会重复计算第100项两次，这将白白浪费许多时间。

实际上，如果我们对递归算法稍作修改，就可以让其变为动态规划的形式，即另加一个用于记忆的数据结构。这种做法叫做记忆化搜索，它本质上就是一种自顶向下的动态规划算法（从大问题到小问题）。如果我们从小问题开始求解，最终递推出所要求的大问题结果，那么这也是一种动态规划的实现方法（自底向上）。有不少博客都将记忆化搜索和自底向上的动态规划区分开来，将后者定义为动态规划，实际上我认为二者都是动态规划的不同实现形式。

如果我们使用动态规划算法，它将在计算的过程中将得到的第100项的结果存储起来，从而避免重复计算，这也是为什么动态规划算法能够大大减少运行时间的原因。

动态规划算法的关键点总结为：

• 动态规划法试图只解决每个子问题一次
• 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 动态规划算法往往还会被拿来和贪心算法比较，但贪心算法只会关注局部最优解，当局部最优无法达到全局最优时，贪心算法将出错。实际上，如何选择各种策略可以总结为：

每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

同时，我们也要注意，尽管动态规划具有无后效性，但并不代表我们不可以用动态规划解决求解需要获取过程组合的问题，例如：140. 单词拆分 II。

0-1背包问题

题目

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是C1i，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

基本思路

最基础的背包问题，每件物品只有1个，也只有一种选择：放或者不放。

我们可以定义状态矩阵：F[i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是：

F[i,v]=maxF[i−1,v],F[i−1,v−Ci]+Wi

简单解析一下上述方程：给定了背包容量 v 的情况下，前 i 个物品恰放入背包的最大总价值这个子问题只需要考虑第 i 个物品是否放入背包。当前物品不放入背包的情况下，当前总价值与前 i -1 个物品恰放入容量 v 的背包的总价值相等；而如果放入背包，则留给前 i-1 个物品将会减小，当前总价值与前 i -1 个物品恰放入容量 v−Ci 的背包的总价值加上当前物品价值Wi相等。 **我们将”给定了背包容量 v 的情况下，前 i 个物品恰放入背包的最大总价值“这个子问题转化为了只和前 i-1 个物品相关的子问题。**同时，我们使用二维数组来存储状态矩阵 F[i, v] ，减少了重叠子问题带来的重复计算时间。

空间复杂度优化

上述问题的空间复杂度为O(VN)，时间复杂度已经达到了最优，但空间复杂度存在着优化空间。

我们通过观察状态转移矩阵发现，第 i 个物品的状态往往只依赖于第 i-1 个物品的状态，那么我们可以很轻松地想到只使用两行数组存储两个时刻的状态，每次更新到 i+1 个物品时，我们让第 i 个物品的状态覆盖第 i-1 个物品的状态，同时让当前物品的状态填充第二行数组即可。这一方法叫做滚动数组法。

但其实，我们可以进一步优化到只使用一行数组来表示状态。观察状态转移方程，我们发现，F[i, v] 只和F[i-1, v]与F[i-1, v-C]有关 ，即当前状态所依赖的子状态，其列数必然小于等于当前状态（v和v-c)。也就是说： 在”填写DP表“的时候，当前行总是参考了它上面一行 “头顶上” 那个位置和“左上角”某个位置的值。因此，我们可以只开一个一维数组，从后向前依次填表即可。

之所以需要从后向前更新状态，是因为我们需要使用到之前的状态。如果从前向后更新，原先的状态F[i-1,v]会被新状态F[i,v]覆盖掉，导致在后面需要使用F[i-1,v]时无法找到，从而出现计算错误。

通过状态压缩，我们可以将空间复杂度优化为O(V)，只用一个数组F[v]解决01背包问题。

• 空间复杂度：O(VN)
• 时间复杂度：O(V)

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果要求恰好装满背包，那么在初始化时除了 F[0] 为 0，其它 F[1..V] 均设为 −∞，这样可以保证最终得到的 F[ V ] 是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 F[0..V ] 全部设为 0。 这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0了。

一个例题

一个01背包问题的实例是：416. 分割等和子集

这道题目的问题是： 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

做这道题需要做这样一个等价转换：是否可以从这个数组中挑选出一些正整数，使得这些数的和等于整个数组元素的和的一半。前提条件是：数组的和一定得是偶数，即数组的和一定得被 2 整除，这一点是特判。 我们将其抽象为01背包问题：每个正整数可以看作是一个价值和重量相等的物品，假设存在一个最大容量为二分之数组元素总和的背包，是否可以挑选一些物品，恰好填满这个背包，也就是这些物品的价值总和等于背包最大容量。

按照01背包问题求解的代码为：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        c=sum(nums)
        if c%2!=0:
            return False
        else:
            c//=2
        dp=[0 for _ in range(c+1)]#状态压缩
        for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算
            dp[j]=nums[0] if j>=nums[0] else 0
        for i in range(1,len(nums)):
            for j in range(len(dp)-1,nums[i]-1,-1):
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])#当前背包容量可以放入的最大价值物品（可以选取的最大整数和）
            if dp[-1]==c:#如果前i个物品恰好能填满容量为c的背包，即可选择一些整数，和为总元素和的一半
                return True
        return False

实际上，我们还可以将01背包问题在本题条件下进一步优化，不需要求解出实际的价值，只需要判断能否选取一些物品填满当前背包容量即可。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        c=sum(nums)
        if c%2!=0:
            return False
        else:
            c//=2
        dp=[0 for _ in range(c+1)]
        for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算
            dp[j]=True if j==nums[0] else False
        for i in range(1,len(nums)):
            for j in range(len(dp)-1,nums[i]-1,-1):
                dp[j]=dp[j] or dp[j-nums[i]]#选或不选当前整数的两种情况下，只要有一种能填满当前背包容量即可将当前状态设为True
            if dp[-1]:#如果dp[c]为True，则说明可以选择一些整数，和为总元素和的一半
                return True
        return False

完全背包问题

题目

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是C1i，得到的价值是Wi。每个物品有无限个可用。求解将哪些物品装入背包可使价值总和最大。

基本思路

完全背包问题看上去只和01背包问题有很小的区别，区别在于完全背包问题每种物品可选的数目是任意的。

我们很容易想到一种贪心的思路：优先选择性价比较高的物品。但仍旧有一个问题，那就是同一种物品虽然可以选择任意多件，但仍旧只能以件为单位，也就是说单个物品是无法拆分的，不能选择半件，只能多选一件或者少选一件。这样就造成了一个问题，往往无法用性价比最高的物品来装满整个背包，比如背包空间为10，性价比最高的物品占用空间为7，那么剩下的空间该如何填充呢？

你当然会想到用性价比第二高的物品填充，如果仍旧无法填满，那就依次用第三、第四性价比物品来填充。

想要举反例很简单，比如只有两个物品：物品A：价值5，体积5，物品B：价值8：体积7，背包容量为10，物品B的性价比显然要比物品A高，那么用贪心算法必然会选择放入一个物品B，此时，剩余的空间已无法装下A或者B，所以得到的最高价值为8，而实际上，选择放入两个物品A即可得到更高的价值10。所以这里贪心算法并不适用。

我们从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……直至取 [V /Ci]件等许多种。 我们基于01背包问题，可以推导出它的动态规划转移公式为：

不难看出，01背包问题是完全背包问题的一种特殊情况。 由于此时需要遍历0到[V /Ci]种策略，所以需要三层枚举，总的时间复杂度为

一个简单有效的优化是：若两件物品 i、j 满足 Ci ≤ Cj 且 Wi≥Wj，则将可以将物品 j 直接去掉，不用考虑。任何情况下都可将价值小费用高的 j 换成物美价廉的 i，得到的方案至少不会更差。这和贪心算法不一样，因为这里不仅要求性价比高，且物品的重量还需要更小。

转化为01背包问题

实际上，我们可以将完全背包问题转化为一个01背包问题，转化的方法为：将一种物品的不同选择次数拆成多件只能选 0 件或 1 件的 01 背包中的物品。

考虑到第 i 种物品最多选[V /Ci]件，于是可以把第 i 种物品转化为 [V /Ci] 件费用及价值均不变的物品。

更进一步优化，我们知道，考虑到二进制数的性质，任意1个数都可以表示为若干个2k的组合。所以，我们只需要将物品拆分为 log[V /Ci] 件物品即可。

空间复杂度优化

与01背包问题类似，完全背包问题的空间复杂度依然可以使用状态压缩进行空间优化。

我们同样可以使用类似的方法将空间复杂度降为O(N)，它和01背包问题唯一的区别在于：不需要反向遍历填充DP表，正向填充即可。

这是因为，01背包问题中，我们最多可以添加1个同种物品，所以我们只能在前 i-1 个物品的结果上进行添加，倒序遍历是防止这个结果被覆盖掉。而完全背包问题中，我们最多可以添加无限个物品，我们可以在前 i 个物品的结果上继续添加，而想要使用前 i 个物品的放置结果，必须正向遍历。

一个例题

一个完全背包问题的实例是：面试题 08.11. 硬币

这道题的目的是： 给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。 很明显，这是一个完全背包问题，背包容量为n，有四种物品，我们可以将它们的价值和重量看作是相同的。这里我们要求的不是最大价值，而是恰好能填满背包的组合数目。

class Solution:
    def waysToChange(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        coins = [1, 5, 10, 25]
        for coin in coins:
            for i in range(1, n+1):
                dp[i] += dp[i-coin] if i-coin>=0 else 0
        return dp[-1] % 1000000007

需要注意的是：常规完全背包问题，可以调换上述两层循环的位置，但是在这道题里不可以，会导致重复的组合，而先遍历币值可以保证结果组合的币值升序，从而不会重复。