Knapsack

背包问题，使用动态规划求解。

分类

有 num 个物品和容量为 weight 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 或 1 个，则为 0-1 背包问题；如果不限定每种物品的数量，则为无界背包问题或完全背包问题。

状态矩阵使用二维数组，dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。

0-1 背包

每件物品只能选择拿或不拿。状态转移方程为

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)  (if j >= w)
           dp[i-1][j]                         (if j < w)

可以进行空间压缩，使用一维的 dp 数组，内层需要逆向遍历。

def knapsack(weights: list[int], values: list[int], int weight_goal):
    dp = [0 for _ in range(w + 1)]
    for w in weights:
        for j in reversed(range(w, weight_goal + 1)):
            #    ^^^ 逆向遍历
            dp[j] = max(dp[j], dp[j-w] + values[i])
    return dp[weight_goal]

完全背包

一个物品可以拿多次。状态转移方程为

dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)  (if j >= w)
           dp[i-1][j]                       (if j < w)

和 0-1 背包相比，仅仅是把状态转移方程中的第二个 i-1 变成了 i。在进行空间压缩时，内层正向遍历

def knapsack(weights: list[int], values: list[int], int weight_goal):
    dp = [0 for _ in range(w + 1)]
    for w in weights:
        for j in range(w, weight_goal + 1):
            dp[j] = max(dp[j], dp[j-w] + values[i])
    return dp[weight_goal]

相关题目

0-1 背包：LeetCode 474. Ones and Zeroes

def count01(s: str) -> (int, int):
    # ...
    return (c0, c1)


class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 空间压缩版本
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for s in strs:
            c0, c1 = count01(s)
            for n0 in reversed(range(c0, m + 1)):
                for n1 in reversed(range(c1, n + 1)):
                    dp[n0][n1] = max(dp[n0 - c0][n1 - c1] + 1, dp[n0][n1])
        return dp[m][n]

    def threeD_findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        slen = len(strs)
        dp = [[[0 for _ in range(n + 1)] for _ in range(m + 1)] for _ in range(slen + 1)]
        # dp[i][n0][n1] = max(dp[i-1][n0-count0(strs[i-1])][n1-count1(strs[i-1])] + 1,
        #                     dp[i-1][n0][n1])
        for i in range(1, slen + 1):
            c0, c1 = count01(strs[i - 1])
            # NOTE: n0 and n1 starts at 0, not 1
            for n0 in range(m + 1):
                for n1 in range(n + 1):
                    if n0 >= c0 and n1 >= c1:
                        dp[i][n0][n1] = max(dp[i - 1][n0 - c0][n1 - c1] + 1, dp[i - 1][n0][n1])
                    else:
                        dp[i][n0][n1] = dp[i - 1][n0][n1]
        return dp[slen][m][n]

完全背包：LeetCode 322. Coin Change

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf') for _ in range(amount + 1)]
        dp[0] = 0
        for c in coins:
            for am in range(c, amount + 1):
                dp[am] = min(dp[am], dp[am - c] + 1)
        return -1 if dp[amount] == float('inf') else dp[amount]

这里初始值设为无穷是为了方便进行 min。