[LeetCode-Python版]动态规划——0-1背包和完全背包问题总结
0-1背包有n个物品，第i个物品的体积为 w i w_i wi，代价为 v i v_i vi，每个物品至多选一个，求体积和不凌驾 capacity 时的最大代价和
状态转移：
d f s ( i , c ) = m a x ( d f s ( i − 1 , c ) , d f s ( i − 1 , c − w [ i ] ) + v [ i ] dfs(i,c)=max (dfs(i- 1,c),dfs(i- 1,c- w) + v dfs(i,c)=max(dfs(i−1,c),dfs(i−1,c−w)+v
常见变形
[*]至多装 capacity，求方案数/最大代价和
[*]恰恰装 capacity，求方案数/最大/最小代价和
[*]至少装 capacity，求方案数/最小代价和
处理求“方案数”、“最大代价和”和“最小代价和”这三种情况时，代码的主要区别在于状态转移方程。
（方案数是＋，最大代价和求max，最小代价和求min）
[*] 方案数： d f s ( i , c ) = d f s ( i − 1 , c ) + d f s ( i − 1 , c − w [ i ] ) dfs(i,c)= dfs(i- 1,c)+dfs(i- 1,c- w) dfs(i,c)=dfs(i−1,c)+dfs(i−1,c−w)
[*] 最大代价和： d f s ( i , c ) = m a x ( d f s ( i − 1 , c ) , d f s ( i − 1 , c − w [ i ] ) + v [ i ] dfs(i,c)=max (dfs(i- 1,c),dfs(i- 1,c- w) + v dfs(i,c)=max(dfs(i−1,c),dfs(i−1,c−w)+v
[*] 最小代价和： d f s ( i , c ) = m i n ( d f s ( i − 1 , c ) , d f s ( i − 1 , c − w [ i ] ) + v [ i ] dfs(i,c)=min (dfs(i- 1,c),dfs(i- 1,c- w) + v dfs(i,c)=min(dfs(i−1,c),dfs(i−1,c−w)+v
例子
[*] 目的和
求恰恰装capacity的方案数
class Solution:
def findTargetSumWays(self, nums: List, target: int) -> int:
# dfs(i,t) = dfs(i-1,t+nums)+dfs(i-1,t-nums)
# 加正号的数和为p
# 加负号的就是所有数的和s减去加正号的数p s-p是所有负数不带负号的累加和
# 这里的p和（s-p）代表的是正1和负1的个数，是个数！！！
# target = p - (s-p)
# 2p = s+target
# p = (s+target)/2 s+t 必然是一个正的偶数
s_add_t = sum(nums)+target
if s_add_t <0 or s_add_t%2:
return 0
s_add_t//=2
n = len(nums)
@cache
def dfs(i,t):
if i<0:
return 1 if t==0 else 0
if t<nums:
returndfs(i-1,t)
return dfs(i-1,t)+dfs(i-1,t-nums)
return dfs(n-1,s_add_t)
[*] 和为目的值的最长子序列的长度
恰恰装capacity的最大代价和
但是这题用记忆化搜索做会超时超内存
class Solution:
def lengthOfLongestSubsequence(self, nums: List, target: int) -> int:
n = len(nums)
@cache
def dfs(i,c):
if i<0:
return 0 if c==0 else -inf
if c<nums:
return dfs(i-1,c)
return max(dfs(i-1,c),dfs(i-1,c-nums)+1)
res = dfs(n-1,target)
dfs.cache_clear() # 不加会超出内存限制
return res if res>-inf else -1
[*] 分割等和子集
恰恰装capacity的方案数（变体，只要有一个就返回True）
class Solution:
def canPartition(self, nums: List) -> bool:
n = len(nums)
s = sum(nums)
if s%2: return False
target = s/2
@cache
def dfs(i,c):
if i<0:
return c==0
if c<nums:
return dfs(i-1,c)
return dfs(i-1,c) or dfs(i-1,c-nums)
return dfs(n-1,target)
完全背包
有n个物品，第i个物品的体积为 w i w_i wi，代价为 v i v_i vi，每种物品无限次重复选，求体积和不凌驾 capacity 时的最大代价和
d f s ( i , c ) = m a x ( d f s ( i − 1 , c ) , d f s ( i , c − w [ i ] ) + v [ i ] dfs(i,c)=max (dfs(i- 1,c),dfs(i,c- w) + v dfs(i,c)=max(dfs(i−1,c),dfs(i,c−w)+v
常见变形
[*]至多装 capacity，求方案数/最大代价和
[*]恰恰装 capacity，求方案数/最大/最小代价和
[*]至少装 capacity，求方案数/最小代价和
处理求“方案数”、“最大代价和”和“最小代价和”这三种情况时，代码的主要区别在于状态转移方程。
（和0-1背包的唯一区别是选的情况的i-1改成i，因为可以重复选）
[*] 方案数： d f s ( i , c ) = d f s ( i − 1 , c ) + d f s ( i , c − w [ i ] ) dfs(i,c)= dfs(i- 1,c)+dfs(i,c- w) dfs(i,c)=dfs(i−1,c)+dfs(i,c−w)
[*] 最大代价和： d f s ( i , c ) = m a x ( d f s ( i − 1 , c ) , d f s ( i , c − w [ i ] ) + v [ i ] dfs(i,c)=max (dfs(i- 1,c),dfs(i,c- w) + v dfs(i,c)=max(dfs(i−1,c),dfs(i,c−w)+v
[*] 最小代价和： d f s ( i , c ) = m i n ( d f s ( i − 1 , c ) , d f s ( i , c − w [ i ] ) + v [ i ] dfs(i,c)=min (dfs(i- 1,c),dfs(i,c- w) + v dfs(i,c)=min(dfs(i−1,c),dfs(i,c−w)+v
例子
[*]零钱兑换
求恰恰装capacity的最小代价和class Solution:
def coinChange(self, coins: List, amount: int) -> int:
# 硬币的面值 表示容量 然后硬币数量 每次选的话 就是1 相当于结果数
n = len(coins)
@cache
def dfs(i,c):
if i<0:
return 0 if c==0 else inf
if c<coins:
return dfs(i-1,c)
return min(dfs(i-1,c),dfs(i,c-coins)+1)
res = dfs(n-1,amount)
return res if res<inf else -1
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]