AI summary
type
status
date
slug
summary
category
tags
icon
password

0-1 背包

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]。现在让你用这个背包装物品，每个物品只能用一次，在不超过背包容量的前提下，最多能装的价值是多少？

贪心解法（非最优）

按照单位价值排序，优先选择单位价值高的。
不是最优的例子：背包容量 10，物品价值为 [6,4,4], 物品重量为 [6,5,5]，贪心算法会选单位价值最高的物品1，获得价值6，但是放了1就放不下其他的了。最优解应该是放物品2和3，获得价值8。
稍微修改一下就能得到一个 2-近似算法，按单位价值排序放，碰到第一个装不下的物品，如果他的价值比包里的价值大，则倒掉包里的换成他。
证明：

动态规划

dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。
根据这个定义，我们想求的最终答案就是 dp[N][W]。base case 就是 dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。
状态转移就是选择是否装入物品i。

子集背包问题

来看看背包问题的思想能够如何运用到其他算法题目。

分割等和子集

输入一个只包含正整数的非空数组 nums，请你写一个算法，判断这个数组是否可以被分割成两个子集，使得两个子集的元素和相等。
对于这个问题，看起来和背包没有任何关系，为什么说它是背包问题呢？
我们可以先对集合求和，得出 sum，把问题转化为背包问题：
给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？
你看，这就是背包问题的模型，甚至比我们之前的经典背包问题还要简单一些，下面我们就直接转换成背包问题，开始套前文讲过的背包问题框架即可。
dp[i][j] = x 表示，对于前 i 个物品（i 从 1 开始计数），当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。
由于 dp 数组定义中的 i 是从 1 开始计数，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]，这一点不要搞混。

完全背包问题

力扣第 322 题「零钱兑换 I」在前文作为经典动态规划的例题讲过。本文讲的零钱兑换 II 是另一种典型背包问题的变体。

零钱兑换Ⅱ

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
我们可以把这个问题转化为背包问题的描述形式：
有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？
这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，无非就是状态转移方程有一点变化而已。
dp[i][j] 的定义如下：
若只使用前 i 种物品，当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。
base case 为 dp[0][..] = 0, dp[..][0] = 1。i = 0 代表不使用任何硬币面值，这种情况下显然无法凑出任何金额；j = 0 代表需要凑出的目标金额为 0，那么什么都不做就是唯一的一种凑法。
我们最终想得到的答案就是 dp[N][amount]
状态转移还是分两种情况取较优者：
如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i-1] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。
如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i-1] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。
有的读者在这里可能会有疑问，不是说可以重复使用硬币吗？那么如果我确定「使用第 i 个面值的硬币」，我怎么确定这个面值的硬币被使用了多少枚？简单的一个 dp[i][j-coins[i-1]] 可以包含重复使用第 i个硬币的情况吗？
对于这个问题，建议你再仔回头细阅读一下我们对 dp 数组的定义，然后把这个定义代入 dp[i][j-coins[i-1]] 看看：
若只使用前 i 个物品（可以重复使用），当背包容量为 j-coins[i-1]时，有 dp[i][j-coins[i-1]] 种方法可以装满背包。
看到了吗，dp[i][j-coins[i-1]] 也是允许你使用第 i 个硬币的，所以说已经包含了重复使用硬币的情况，你一百个放心。

变体：目标和

我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。
那么，回溯算法和动态规划到底是啥关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及「状态」以及做「选择」，是否可能互相转化呢？

目标和

给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

回溯算法

一眼可以用回溯解法，任何算法的核心都是穷举，回溯算法就是一个暴力穷举算法。复习一下回溯算法框架：
关键就是搞清楚什么是「选择」，而对于这道题，「选择」不是明摆着的吗？对于每个数字 nums[i]，我们可以选择给一个正号 + 或者一个负号 -，然后利用回溯模板穷举出来所有可能的结果，数一数到底有几种组合能够凑出 target 不就行了嘛？
等价于二叉树遍历，时间复杂度为 。

动态规划

上面的解法显然有很多重叠子问题被重复计算了。如果从回溯算遍历多叉树的视角来看，消除重叠子问题有些困难，我们可以换个角度，从分解问题（动态规划）的思路来看，就容易使用备忘录消除重叠子问题了。
定义 dp 函数表示使用 nums[i:] 这些元素，能够组成和为 remain 的方法数量，这样就可以用备忘录技巧进行优化了。
这道题有两个状态 i 和 remain，一般来说我们可以用二维数组来充当备忘录。但这道题 remain 可能为负数，所以可以用哈希表作为备忘录，把「状态」转化为字符串作为哈希表的键。或者对 remain 加一个偏移量，使其非负，这样就可以用二维数组了。当然，Python 可以直接用元组作 key，很方便。
这个解法通过备忘录消除了很多重叠子问题，效率有一定的提升，但是这就结束了吗？

背包问题

其实，这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。动态规划总是这么玄学，让人摸不着头脑…
首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：
综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？
现在实现这么一个函数：
然后，可以这样调用这个函数：
好的，变成背包问题的标准形式：
有一个背包，容量为 sum，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]（注意 1 <= i <= N），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包？
现在，这就是一个正宗的动态规划问题了，下面按照我们一直强调的动态规划套路走流程：
第一步要明确两点，「状态」和「选择」。
对于背包问题，这个都是一样的，状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
按照背包问题的套路，可以给出如下定义：
dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。
翻译成我们探讨的子集问题就是，若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。
根据这个定义，显然 dp[0][..] = 0，因为没有物品的话，根本没办法装背包；但是 dp[0][0] 应该是个例外，因为如果背包的最大载重为 0，「什么都不装」也算是一种装法，即 dp[0][0] = 1。
为什么 base case 不是像之前的背包问题一样取 dp[..][0] = 1 呢？即背包容量为 0 时，只有「什么都不装」这一种装法。这里不能这样初始化，是因为本题 nums 数组中的元素是可能为 0 的，那么背包容量为 0 时，「什么都不装」可能就不是唯一的装法了，而需要在状态转移的过程中具体去计算。
我们所求的答案就是 dp[N][sum]，即使用所有 N 个物品，有几种方法可以装满容量为 sum 的背包。
第三步，根据「选择」，思考状态转移的逻辑。
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。
由于 dp[i][j] 为装满背包的总方法数，所以应该以上两种选择的结果求和。
代码如下：
然后，发现这个 dp[i][j] 只和前一行 dp[i-1][..] 有关，那么肯定可以优化成一维。注意 j 要从后往前遍历，不然 dp[i-1][j-1] 就被覆盖为 dp[i][j-1] 了。