背包问题

作为一类极其重要的动态规划问题，将其单独分类。

0-1 背包

01-背包：板子题

给定件物品，其体积与重量分别为和。求在总体积的限制下，能够装下的最大重量。

def bag_01(V, volumes, weights):
    """
    给定n件物品的体积与价值,考虑总体积<=V时,能够获得的最大价值
    """
    n = len(volumes)
    # 考虑前i件物品，容量不超过j时的最大价值
    dp = [[0 for _ in range(V + 1)] for _ in range(n + 1)]  
    for i in range(1, n + 1):
        for j in range(V + 1):
            volume, weight = volumes[i-1], weights[i-1]
            pick = dp[i-1][j-volume] + weight if j>=volume else 0    # 能选 or 不能选
            not_pick = dp[i-1][j]
            dp[i][j] = max(pick, not_pick)                           # 选 or 不选
    return dp[-1][-1]

• 时间复杂度：
• 空间复杂度：

def bag_01_opt(V, volumes, weights):
    dp = [0 for _ in range(V + 1)]
    for volume, weight in zip(volumes, weights):
        for j in range(V + 1):
            pick = dp[j - volume] + weight if j >= volume else 0
            not_pick = dp[j]
            dp[j] = max(pick, not_pick)
    return dp[-1]

• 时间复杂度：
• 空间复杂度：

416. Partition Equal Subset Sum

：使用的所有元素，能否凑到金额。
由于每个数字只能使用一次，故转化为0-1背包问题。

• 选择num，

• 不选择num，不变

  class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if (total := sum(nums)) & 1:
            return False
        target = total // 2
        n = len(nums)
        # dp[i][j]: 使用前i个数字，能否恰好凑到和j
        dp = [[True] + [False] * (target) for _ in range(n + 1)]
        for i in range(1, n + 1):
            num = nums[i-1]
            for j in range(1, target + 1):
                # 选第i个数字 => 前i-1个数字能否凑到和j-num
                pick = dp[i-1][j-num] if j >= num else False    
                not_pick = dp[i-1][j]    # 不选第i个数字
                dp[i][j] = pick or not_pick
        return dp[-1][-1]

• 时间复杂度：

• 空间复杂度：

  class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total & 1:
            return False
        target = total // 2             # 建模：等分数组 => 能否凑到数组的一半
        dp = [True] + [False] * target  # 滚动数组
        for num in nums:
            for j in range(target, num-1, -1):  # 倒序遍历，注意范围
                dp[j] |= dp[j - num]
        return dp[-1]

• 时间复杂度：

• 空间复杂度：

474. Ones and Zeroes

：考虑前个字符串，背包容量为个和个时，能容纳的字符串数量最大值。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[[0] * (n+1) for _ in range(m+1)] for __ in range(len(strs)+1)]
        for i in range(1, len(strs) + 1):
            zeros = strs[i-1].count('0')
            ones  = len(strs[i-1]) - zeros
            for j in range(m + 1):
                for k in range(n + 1):
                    if j < zeros or k < ones:
                        dp[i][j][k] = dp[i-1][j][k]
                    else:
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1)
        return dp[-1][-1][-1]

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n+1) for _ in range(m+1)]
        for s in strs:
            zeros = s.count('0')
            ones  = len(s) - zeros
            for i in range(m, zeros-1, -1):
                for j in range(n, ones-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)
        return dp[-1][-1]

from functools import lru_cache
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        @lru_cache(None)
        def dfs(i, m, n):
            if i == len(strs):
                return 0
            zeros = strs[i].count('0')
            ones  = len(strs[i]) - zeros
            not_pick = dfs(i + 1, m, n)
            pick = dfs(i + 1, m - zeros, n - ones) + 1 if m >= zeros and n >= ones else 0
            return max(not_pick, pick)
        return dfs(0, m, n)

494. Target Sum

在背包容量为的限制下，求装满背包的总方案数。注意容量为的背包初始化方案数为1。
特判：

1. 不可整除；

2. 的绝对值超过了，即全部置为正数，也不能满足要求。

   class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n, total = len(nums), sum(nums)
        if abs(target) > total or (total + target) & 1:
            return 0
        pos_sum = (total + target) // 2
        # dp[i]: 凑成和为i的正数的方案数
        dp = [1] + [0] * pos_sum
        for num in nums:
            for i in range(pos_sum, num-1, -1): # target -> num 逆向遍历
                dp[i] += dp[i - num]
        return dp[-1]

• 时间复杂度：
• 空间复杂度：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @lru_cache(None)
        def dfs(idx, total):
            if idx == len(nums):
                return 1 if total == target else 0
            pos = dfs(idx + 1, total + nums[idx])
            neg = dfs(idx + 1, total - nums[idx])
            return pos + neg
        return dfs(0, 0)

• 时间复杂度：，遍历所有种表达式，每个表达式计算结果需要的时间
• 空间复杂度：，取决于递归调用栈的深度

完全背包

完全背包：板子题

有件物品和一个容量为的背包，每件物品有无限件；第件物品的体积和质量分别为和。
求解如何将物品装入背包，能够使得容纳相应物品的情况下，装下的质量最大。

def bag_cmp(N, C, volumes, weights):
    # 考虑前i件物品，装入容量为j的背包 => 最大价值W:dp[i][j]
    dp = [[0 for _ in range(C + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        volume, weight = volumes[i-1], weights[i-1]
        for j in range(C + 1):
            pick = dp[i][j-volume] + weight if j >= volume else 0  # 同一row进行转移
            not_pick = dp[i-1][j]
            dp[i][j] = max(pick, not_pick)
    return dp[-1][-1]

def bag_cmp_opt(N, C, volumes, weights):
    dp = [0 for _ in range(C + 1)]
    for volume, weight in zip(volumes, weights):
        for j in range(volume, C + 1):            # 起点为volume
            pick = dp[j - volume] + weight
            not_pick = dp[j]
            dp[j] = max(pick, not_pick)
    return dp[-1]

322. Coin Change

：（考虑前枚硬币，可复用）填满容量为的背包需要的最少硬币数量。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [10001] * amount
        for coin in coins:
            for j in range(coin, amount+1):
                dp[j] = min(dp[j], 1 + dp[j-coin])
        return dp[-1] if dp[-1] != 10001 else -1

• 时间复杂度：
• 空间复杂度：

518. Coin Change 2

：（考虑前枚硬币，可复用）填满容量为的背包的最多方案数。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [1] + [0] * amount
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]
        return dp[-1]

• 时间复杂度：
• 空间复杂度：

279. Perfect Squares

class Solution:
    def numSquares(self, n: int) -> int:
        # dp[j]:凑成数字j需要的最少正整数数量
        dp = [0] * (n + 1)
        for i in range(n + 1):
            dp[i] = i
        for i in range(2, 100 + 1):    # i:当前选择的正整数[1, 100]
            if i**2 > n:
                break
            for j in range(i**2, n + 1):
                dp[j] = min(dp[j], dp[j-i**2] + 1)
        return dp[-1]

• 时间复杂度：
• 空间复杂度：