OJ刷题总结 7
OJ刷题总结7——0-1背包 完全背包
1. 0-1背包
有 $n$ 个物品 第 $i$ 个物品的体积为 $w[i]$ ,价值为 $v[i]$每个物品至多选一个,求体积和不超过 capacity 时的最大价值和
回溯三问:
- 当前操作?枚举第
i
个物品选或不选- 不选,剩余容量不变
- 选,剩余容量减少
w[i]
- 子问题?在剩余容量为
c
时,从前i
个物品中得到的最大价值和 - 下一个子问题?分类讨论:
- 不选:在剩余容量为
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 | def zero_one_bag(capacity, w, v): |
常见变形
- 至多装
capacity
,求方案数/最大价值和 - 恰好装
capacity
,求方案数/最大/最小价值和 - 至少装
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class 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)
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)递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class 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]优化空间
我们可以发现,算完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
25class 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]超级优化空间
我们可以只用一个数组吗?
也就是说将
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
23class 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 时的最大价值和
回溯三问:
- 当前操作?枚举第
i
个物品选或不选- 不选,剩余容量不变
- 选,剩余容量减少
w[i]
- 子问题?在剩余容量为
c
时,从前i
个物品中得到的最大价值和 - 下一个子问题?分类讨论:
- 不选:在剩余容量为
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 | def unbounded_knapsack(capacity: int, w: List[int], v: List[int]) -> int: |
常见变形:
- 至多装
capacity
,求方案数/最大价值和 - 恰好装
capacity
,求方案数/最大/最小价值和 - 至少装
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])
忽然发现回溯可能没学好,回去重学了