背包DP

问题描述

基本背包问题

背包问题（Knapsack Problem）描述的是有容量约束的情况下，求考虑了所有物品（大小价值各异）之后的最优解或解的个数。[背包问题九讲]

首先来总结，如果我们要求的是背包中能装的最大价值。我们用以下变量来表示：

• $v_i$ ：物品$i$ 的大小

• $w_i$ ：物品 $i$ 的价值

• $V:$ 背包总容量

• $f[j]$ 表示容量为 $j$ 的背包的答案，最后返回答案 $f[V]$。

两种基本的背包问题：

1. 0-1背包：每个物品只能拿一次

2. 完全背包：每个物品能拿无限次

背包方法	转移方程（空间压缩后）	容量$j$的遍历顺序
0-1背包	$f[j] = \max_{i}(f[j-v_i] + w_i)$	$j\text{ 倒序 } V \text{ to } v_i$
完全背包	$f[j] = \max_{i}(f[j-v_i] + w_i)$	$j\text{ 正序 } v_i \text{ to } V$

# 0-1背包：因为利用到本行信息，倒序保证安全更新
for n in nums:
    for j in range(V, n-1, -1):

# 完全背包：因为利用到上一行信息，正序保证及时更新
for n in nums:
    for j in range(n, V+1):

在循环中是业务逻辑，有时候我们不是求最大最小值，而是求可行性或者方案数。

f[j] = max(f[j], f[j-n]+v) # 最值
f[j] += f[j-n] # 方案数
f[j] |= f[j-n] # 可行性

其中0-1背包和完全背包的转移方程是一样的，唯一区别是容量变量 $j$ 的遍历方向。

遍历方向解释

能够这样做的原因是因为转移方程依赖哪一行的结果，之后我们看了二维（空间压缩前的转移方程）就明白了，图示如下：

• 0-1背包：因为利用到本行信息，倒序保证安全更新

• 完全背包：因为利用到上一行信息，正序保证及时更新

乍一看背包问题有可能觉得是用DFS求解，每次考虑是否装入某个物品。虽然用了记忆化优化后也能有效求解，但我觉得用背包DP求解会更容易理解。

初始化 $f$ 有两种情况：

• 求背包中能装的最大价值，初始$f[0, ..., V]=0$

• 求装满背包的最大价值，初始$f[0]=0, f[1, ..., V]=-\infty$

  • 或者可行性解决初始化： $f[0]=\text{True}, f[1, ..., V]=\text{False}$

  • 可以这么考虑：考虑了0个物品后，什么都不装 = 装满容量为0的背包

延伸背包问题

1. 多维费用背包：如果背包有多种容量限制（比如长和宽），每个物品有多个维度体积，那么可以“费用“这个维度可以扩展开来。如果每个物品只能拿一次，维度=2，那么就是二维费用0-1背包问题，

2. 分组背包：如果所有物品被划分成 $K$ 组，每组最多只能拿一个物品

背包方法	转移方程（空间压缩后）	容量$j$的遍历顺序
二维0-1背包	$f[j][k] = \max_{i}(f[j-v_i][k-u_i] + w_i)$	$j\text{ 倒序 } V \text{ to } v_i \\ k\text{ 倒序 } V \text{ to } u_i$
分组背包	$f[j] = \max(f[j-v_i] + w_i) \\ | \text{item}_i \in \text{group } k$	$k\text{ 正序 } 1 \text{ to } K$ $j\text{ 倒序 } V \text{ to } 0$

# 考虑元素之间顺序的组合问题
for j in range(1, V+1):
    for n in nums:

# 二维费用0-1背包：
for n, n2 in nums:
    for j in range(m, n1-1, -1):
        for k in range(n, n2-1, -1):

# 分组背包：第三层循环顺序保证每组最多拿一个物品
for k in range(K):
    for j in range(V, -1, -1):
        for n in nums[k]:

例题

0-1背包

空间压缩前的转移方程：

$f[i][j] = \begin{cases} \text{不拿物品}i&:& f[i-1][j] \\ \text{拿物品}i &:& f[i-1][j-v_i] + w_i \\ \end{cases}$

• 目标和：转化问题以后为0-1背包方案数问题。每个物品只能拿一次，有几种装满背包的方案？

• 分割等和子集：转化后为0-1背包可行性问题。每个物品只能拿一次，是否能正好装满背包。

• 最后一块石头的重量 II：转化后为0-1背包最小值问题。

目标和

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

def findTargetSumWays(nums, target):
    # n0+n1+...-n3-n4 = target =>
    # 2*(n0+n1+...) = target + sum
    # 0-1 knapsack with capacity = (target+sum) // 2
    s = sum(nums)
    if (target+s)&1 or target>s: return 0

    V = (target + s) >> 1
    f = [1] + [0]*V
    for n in nums:
        for j in range(V, n-1, -1):
            f[j] += f[j-n]
    return f[-1]

分割等和子集

最后一块石头的重量 II

完全背包

空间压缩前的转移方程：唯一的区别在于拿了物品 $i$ 以后不急着增加 $i$，因为你还有机会拿$i$。

$f[i][j] = \begin{cases} \text{不拿物品}i&:& f[i-1][j] \\ \text{拿物品}i &:& f[i][j-v_i] + w_i \\ \end{cases}$

• 零钱兑换：完全背包最小值

• 零钱兑换 II：完全背包方案数

• 完全平方数：完全背包最小值

• 组合总和 Ⅳ：考虑物品顺序的完全背包方案数。每个物品可以重复拿，有几种装满背包的方案？

零钱兑换

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

def coinChange(nums, V):
    f = [0] + [float('inf')]*V
    for n in nums:
        for j in range(n, V+1):
            f[j] = min(f[j], f[j-n]+1)
    return f[-1] if f[-1]<float('inf') else -1

零钱兑换 II

完全平方数

组合总和 Ⅳ

二维费用0-1背包

$f[i][j][k] = \begin{cases} \text{不拿物品}i&:& f[i-1][j][k] \\ \text{拿物品}i &:& f[i-1][j-v_i][k-u_i] + w_i \\ \end{cases}$

• 01 字符构成最多的字符串：多维费用的 0-1 背包最大值，有两个背包大小，0 的数量和 1 的数量。

• 盈利计划：多维费用的 0-1 背包最大值

01 字符构成最多的字符串

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，
该子集中 最多 有 m 个 0 和 n 个 1 。

输入：strs = ["10", "0001", "111001", "1", "0"],
     m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 
     {"10","0001","1","0"} 因此答案是 4 。
     其他满足题意但较小的子集包括{"0001","1"} 和 {"10","1","0"} 。
     {"111001"}不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

def findMaxForm(strs, m, n):
    f = [[0]*(n+1) for _ in range(m+1)]
    for s in strs:
        c1, c0 = s.count("0"), s.count("1")
        for i in range(m, c1-1, -1):
            for j in range(n, c0-1, -1):
                f[i][j] = max(f[i][j],
                              f[i-c1][j-c0]+1)
    return f[-1][-1]

盈利计划

分组背包

$f[k][j] = \begin{cases} \text{不拿第k组}&:& f[k-1][j] \\ \text{拿第k组}i &:& f[k-1][j-v_i] + w_i | \text{item}_i \in \text{group } k \\ \end{cases}$

掷骰子的N种方法：每一组是一个骰子，每个骰子只能拿一个体积为1到6的物品

这里有 d 个一样的骰子，每个骰子上都有 f 个面
分别标号为 1, 2, ..., f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况.

输入：d = 1, f = 6, target = 3
输出：1

def numRollsToTarget(n, maxpoints, V):
    MOD = 10**9 + 7
    f = [1] + [0]*V
    for i in range(n):
        for j in range(V, i-1, -1):
            f[j] = 0
            for k in range(1, min(maxpoints, j)+1):
                f[j] = (f[j] + f[j-k]) % MOD
    return f[-1]