OJ刷题总结7——0-1背包 完全背包

1. 0-1背包

有 $n$ 个物品 第 $i$ 个物品的体积为 $w[i]$ ，价值为 $v[i]$每个物品至多选一个，求体积和不超过 capacity 时的最大价值和

回溯三问：

  1. 当前操作？枚举第i个物品选或不选
    • 不选，剩余容量不变
    • 选，剩余容量减少w[i]
  2. 子问题？在剩余容量为c时，从前i个物品中得到的最大价值和
  3. 下一个子问题？分类讨论：
    • 不选：在剩余容量为c时，从前i-1个物品中得到的最大价值和
    • 选：在剩余容量为c-w[i]时，从前i-1个物品中得到的最大价值和

dfs(i, c) = max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])

Code:

1
2
3
4
5
6
7
8
9
10
11
12
def zero_one_bag(capacity, w, v):
    n = len(w)

    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        if c < w[i]:
            return dfs(i-1, c)
        return max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i])
    
    return dfs(n - 1, capacity)

常见变形

  1. 至多装capacity，求方案数/最大价值和
  2. 恰好装capacity，求方案数/最大/最小价值和
  3. 至少装capacity，求方案数/最小价值和

方案数：dfs(i, c) = dfs(i - 1, c) + dfs(i - 1, c - w[i])

时间复杂度：$O(n \cdot (target + s))$

空间复杂度：$O(n \cdot (target + s))$

进一步优化空间复杂度：

==记忆化搜索可以1:1翻译成递推==，做法就是把dfs函数改成f数组，递归改成循环就好了

f[i][c] = f[i-1][c] + f[i - 1][c - w[i]]
为了防止下标越界，可以把f的下标+1：
f[i + 1][c] = f[i][c] + f[i][c - w[i]]

494

  1. 记忆化搜索

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution:
        def findTargetSumWays(self, nums: List[int], target: int) -> int:
            '''
            正数：p
            负数：s-p
            p - (s - p) = t
            2p = s + t
            p = (s + t) / 2
            '''
            target += sum(nums)
            if target < 0 or target % 2:
                return 0
            target //= 2

            n = len(nums)

            @cache
            def dfs(i, c):
                if i < 0:
                    return 1 if c == 0 else 0
                if c < nums[i]:
                    return dfs(i-1, c)
                return dfs(i-1, c) + dfs(i-1, c-nums[i])

            return dfs(n - 1, target)

  2. 递推

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution:
        def findTargetSumWays(self, nums: List[int], target: int) -> int:
            '''
            正数：p
            负数：s-p
            p - (s - p) = t
            2p = s + t
            p = (s + t) / 2
            '''
            target += sum(nums)
            if target < 0 or target % 2:
                return 0
            target //= 2

            n = len(nums)

            f = [[0] * (target + 1) for _ in range(n + 1)]
            f[0][0] = 1
            for i, x in enumerate(nums):
                for c in range(target + 1):
                    if c < x:
                        f[i + 1][c] = f[i][c]
                    else:
                        f[i + 1][c] = f[i][c] + f[i][c - x]
            return f[n][target]

  3. 优化空间

    我们可以发现，算完f[i + 1]后，f[i]就没用了。 也就是说，每时每刻，只有2个数组中的元素是参与状态转移。那么，就干脆只用两个数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution:
        def findTargetSumWays(self, nums: List[int], target: int) -> int:
            '''
            正数：p
            负数：s-p
            p - (s - p) = t
            2p = s + t
            p = (s + t) / 2
            '''
            target += sum(nums)
            if target < 0 or target % 2:
                return 0
            target //= 2

            n = len(nums)

            f = [[0] * (target + 1) for _ in range(2)]
            f[0][0] = 1
            for i, x in enumerate(nums):
                for c in range(target + 1):
                    if c < x:
                        f[(i + 1) % 2][c] = f[i % 2][c]
                    else:
                        f[(i + 1) % 2][c] = f[i % 2][c] + f[i % 2][c - x]
            return f[n % 2][target]

  4. 超级优化空间

    我们可以只用一个数组吗？

    也就是说将f[i + 1][c] = f[i][c] + f[i][c - w[i]]写成：

    f[c] = f[c] + f[c - w[i]]，我们来动手算算：

    举一个例子：

    w[i] = 2

    i : 1 2 3 5 6 7 9

    i + 1: 1 2 4 7 10

    注意，前向遍历，由于在前面就已经更新过f[2]了，所以在更新f[4]时用的元素是已经更好了的，所以会不对。

    但是，如果说，我们从后往前遍历，就不会有这种错误发生

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution:
        def findTargetSumWays(self, nums: List[int], target: int) -> int:
            '''
            正数：p
            负数：s-p
            p - (s - p) = t
            2p = s + t
            p = (s + t) / 2
            '''
            target += sum(nums)
            if target < 0 or target % 2:
                return 0
            target //= 2

            n = len(nums)

            f = [0] * (target + 1)
            f[0] = 1

            for x in nums:
                for c in range(target, x - 1, -1):
                    f[c] = f[c] + f[c - x]
            return f[target]

2. 完全背包

有 $n$ 种物品，第 $i$ 种物品的体积为 $w[i]$ ，价值为 $v[i]$每种物品无限次重复选，求体积和不超过 capacity 时的最大价值和

回溯三问：

  1. 当前操作？枚举第i个物品选或不选
    • 不选，剩余容量不变
    • 选，剩余容量减少w[i]
  2. 子问题？在剩余容量为c时，从前i个物品中得到的最大价值和
  3. 下一个子问题？分类讨论：
    • 不选：在剩余容量为c时，从前i-1个物品中得到的最大价值和
    • 选：在剩余容量为c-w[i]时，==从前i个物品中得到的最大价值和==

这里和0-1背包不同的地方在于，我选了第i个物品后，我还能继续选。所以子问题中“选”就变成了，“从前i个物品中得到的最大价值和”

dfs(i, c) = max(dfs(i - 1, c), dfs(i, c - w[i]) + v[i])

Code:

1
2
3
4
5
6
7
8
9
10
def unbounded_knapsack(capacity: int, w: List[int], v: List[int]) -> int:
  	n = len(w)
    
    @cache
    def dfs(i, c):
      	if i < 0:
          	return 0
        if c < w[i]:
          	return dfs(i - 1, c)
        return max(dfs(i - 1, c), dfs(i, c - w[i]) + v[i])

常见变形：

  1. 至多装capacity，求方案数/最大价值和
  2. 恰好装capacity，求方案数/最大/最小价值和
  3. 至少装capacity，求方案数/最小价值和

322

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

这个题目，就是变形之一：

恰好+最小

我们可以写出一个递推式：

dfs(i, c) = min(dfs(i - 1, c), dfs(i, c - w[i]) + v[i])

本题中，w指的是coin的面值，v为1（即需要的硬币数）

1:1翻译为数组形式：

f[i][c] = min(f[i - 1][c], f[i][c - w[i]] + v[i])

忽然发现回溯可能没学好，回去重学了