0x3f第12天 0-1背包

1.0-1背包问题：

#capacity :背包容量

#w[i]：第i个物体的体积

#v[i]：第i个物体的价值

def dfs(i , c): 定义：选或不选到第i个物体时，目前背包最大价值

i:目前装了i个物体 c：背包剩余容量

回溯公式：

dfs（i,c）=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]) 装没装第i个物体的两种情况

边界条件：1.i == 0 没东西可装

2. 剩余容量不足以装下当前的这个w[ i ]

#capacity :背包容量 #w[i]：第i个物体的体积 #v[i]：第i个物体的价值 n = len(w) 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]) dfs(n-1,capacity)

1.1.目标和 问题

1.回溯法+cache

目标和问题可以转换为0-1背包问题，因为最后也是从数组中选出几个数，使其最终和为一个定值

令p：正数和，q：负数和 sums = p-q target = p+q

可以得出 p = （sum+target）//2 即几个数和为定值

dfs（i，t）定义：从i个数中选出和为t的 方案个数

参数i：从包括i及其往前的数字中选

t：现在要凑的目标和

回溯方程：

dfs(i,t) = dfs(i-1,t) + dfs(i-1,t-nums[i])

边界条件：若sum+target并不是偶数，或者为负数，那就无解，返回 0

边界条件：若当前的nums[i] > t，那就加不进去，return dfs(i-1,t)

初始条件：if i < 0: //没有可选的了，从n已经遍历到开头了

if t==0:return 1 此方案可行

else: return 0 没有恰好为t的方案

代码：

时间复杂度：t*n空间复杂度：：n

时间复杂度你可以把这个dfs函数的执行过程，理解成 “填一张 n 行、t 列的表格”：

class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: target = sum(nums)+target n = len(nums) if target%2 != 0 or target<0: return 0 t = target//2 @cache def dfs(i,t): if i<0: if t==0: return 1 else: return 0 if nums[i]>t: return dfs(i-1,t) return dfs(i-1,t) + dfs(i-1,t-nums[i]) return dfs(n-1,t)

2.递推

先根据回溯公式写出f公式：

dfs(i,t) = dfs(i-1,t) + dfs(i-1,t-nums[i])

f[i][t] = f[i-1][t] + f[i-1][t-nums[i]]数组最好不要出现负数情况

f [ i + 1 ] [ t ] = f [ i ] [ t ] + f [ i ] [ t - nums[ i ] ]

于是自然想到建立一个f[[]]二维数组 为了边界条件，我们的二维数组会多一列、一行

公式：f = [ [0] *(t +1) for _ in range(n+1) ] *的是列数量 for的是行数量

n+1对于前0个，1个...n个元素

t 对应 凑出和为0 ，1 ，...t的数

递归变循环，怎么变，取决于f公式需要什么

f [ i + 1 ] [ t ] = f [ i ] [ t ] + f [ i ] [ t - nums[ i ] ] 可以看出需要 i ， t , nums[ i ]

for i,x in enumerate(nums):

for c in range(t+1):

边界条件：nums[i]>t: 在这就是 x>c

时间复杂度：t n 空间复杂度 t n

class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: target = sum(nums)+target n = len(nums) if target%2 != 0 or target<0: return 0 t = target//2 f = [[0]*(t+1)for _ in range(n+1)] f[0][0]=1 for i,x in enumerate(nums): for c in range(t+1): if x>c: f[i+1][c] = f[i][c] else: f[i+1][c] = f[i][c]+f[i][c-x] return f[n][t]

3.空间优化两个数组

发现f[i+1]只取决于f[i]，所以只需要两个数字

之后的数组重新覆盖f0和f1即可

f = [[0]*(t+1)for _ in range(2)] 两行数组

f[i+1]都改成f[(i+1)%2]

f[i]都改成f[i%2]

空间复杂度为 t

4.空间优化一个数组

和i有关的都删掉，遍历target的时候倒着遍历，从t遍历至x，倒序到 x，只处理 c≥x 的场景，避免重复选，最开始的边界条件

时间复杂度 tn 空间复杂度t

class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: target = sum(nums)+target n = len(nums) if target%2 != 0 or target<0: return 0 t = target//2 f =[0]*(t+1) f[0]=1 for x in nums: for c in range(t,x-1,-1): f[c] = f[c]+f[c-x] return f[t]

2.完全背包

每个物品可以重复选，回溯公式修改：

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

dfs (i,c) = min(dfs(i-1,c),dfs(i, c-w[i])+v[i])选了，但还可以选，所以i不变

2.1 零钱兑换

1.回溯法+cache

dfs(i,c)定义：用前i种硬币，凑c块钱，最少用几个硬币

i：前i种硬币

c:还需要凑c块钱

回溯方程：

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

边界条件：

1.若 coins[i]>c，return dfs(i-1,c) 这类硬币滚蛋

2.若i < 0 andc!=0，说明还没凑完，return inf 无解

起始条件：

若 i<0 and c==0,return 0所有硬币都处理完了，且剩余要凑的金额是 0不需要再用任何硬币

i < 0且c == 0→ 返回 0

• 含义：所有硬币都处理完了，且剩余要凑的金额是 0（已经凑够了）；
• 为什么返回 0？因为 “没有硬币可选” 的情况下，凑够了金额 0，不需要再用任何硬币→ 最少硬币数就是 0；
• 举例子：比如你要凑金额 0，不管有没有硬币，都只需要 0 个硬币（啥都不用选），这是所有最值问题的 “基础锚点”。

• class Solution: def coinChange(self, coins: List[int], amount: int) -> int: n = len(coins) @cache def dfs(i,c): if i<0: if c==0:return 0 else: return inf if coins[i] > c: return dfs(i-1,c) return min(dfs(i-1,c),dfs(i,c-coins[i])+1) ans = dfs(n-1,amount) if ans < inf: return ans else: return -1