背包DP

问题描述

基本背包问题

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

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

$v_i$ ：物品 $i$ 的大小
$w_i$ ：物品 $i$ 的价值
$V:$ 背包总容量
$f[j]$ 表示容量为 $j$ 的背包的答案，最后返回答案 $f[V]$ 。

两种基本的背包问题：

0-1背包：每个物品只能拿一次
完全背包：每个物品能拿无限次

背包方法

转移方程（空间压缩后）

容量 $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的背包

延伸背包问题

多维费用背包：如果背包有多种容量限制（比如长和宽），每个物品有多个维度体积，那么可以“费用“这个维度可以扩展开来。如果每个物品只能拿一次，维度=2，那么就是二维费用0-1背包问题，
分组背包：如果所有物品被划分成 $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]

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

def canPartition(nums):
    s = sum(nums)
    if s&1: return False
    
    V = s >> 1
    f = [True] + [False]*V
    for n in nums:
        for j in range(V, n-1, -1):
            f[j] |= f[j-n]
    return f[-1]

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

def lastStoneWeightII(nums):
    # s1-s2+s3-s4+... = sum(s) - 2*(s2+s4+...)
    # maximize subarry sum S=s2+s4+...
    # s2<s1, s4<s3, ... => S<sum(s)//2
    s = sum(nums)
    V = s >> 1
    
    # 0-1 knapsack with capacity=V
    f = [0 for _ in range(V+1)]
    for n in nums:
        for j in range(V, n-1, -1):
            f[j] = max(f[j], f[j-n]+n)
    return s-f[-1]*2

完全背包

空间压缩前的转移方程：唯一的区别在于拿了物品 $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

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

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

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16)
使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

def numSquares(V):
    nums = [i*i for i in range(1, int(V**0.5)+1)]
    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]

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

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

二维费用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 背包最大值

给你一个二进制字符串数组 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]

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，
它要求 group[i] 名成员共同参与。
如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为盈利计划。
并且工作的成员总数最多为 n 。

有多少种计划可以选择？

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，
     或仅完成工作 1 。总的来说，有两种计划。

def profitableSchemes(n, minProfit, group, profit):
    f = [[0]*(n+1) for _ in range(minProfit+1)]
    f[0][0] = 1
    for v, p in zip(group, profit):
        for i in range(minProfit+p, p-1, -1):
            for j in range(n, v-1, -1):
                f[min(minProfit, i)][j] += f[i-p][j-v]
    return sum(f[-1]) % (10**9+7)

分组背包

$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]

Previous区间DP Next状压DP

Last updated 4 years ago

Was this helpful?