[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的方案数
  
  1. class Solution:
  2. def findTargetSumWays(self, nums: List[int], target: int) -> int:
  3.     # dfs(i,t) = dfs(i-1,t+nums[i])+dfs(i-1,t-nums[i])
  4.     # 加正号的数和为p
  5.     # 加负号的就是所有数的和s减去加正号的数p s-p是所有负数不带负号的累加和
  6.     # 这里的p和（s-p）代表的是正1和负1的个数，是个数！！！
  7.     # target = p - (s-p)
  8.     # 2p = s+target
  9.     # p = (s+target)/2 s+t 必然是一个正的偶数
  10.     s_add_t = sum(nums)+target
  11.     if s_add_t <0 or s_add_t%2:
  12.         return 0
  13.     s_add_t//=2
  14.     n = len(nums)
  15.     @cache
  16.     def dfs(i,t):
  17.         if i<0:
  18.             return 1 if t==0 else 0
  19.         if t<nums[i]:
  20.             return  dfs(i-1,t)
  21.         return dfs(i-1,t)+dfs(i-1,t-nums[i])
  22.     return dfs(n-1,s_add_t)

  复制代码
• 和为目的值的最长子序列的长度
  恰恰装capacity的最大代价和
  但是这题用记忆化搜索做会超时超内存
  
  1. class Solution:
  2.     def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
  3.         n = len(nums)
  4.         
  5.         @cache
  6.         def dfs(i,c):
  7.             if i<0:
  8.                 return 0 if c==0 else -inf
  9.             if c<nums[i]:
  10.                 return dfs(i-1,c)
  11.             return max(dfs(i-1,c),dfs(i-1,c-nums[i])+1)
  13.         res = dfs(n-1,target)
  14.         dfs.cache_clear() # 不加会超出内存限制
  15.         return res if res>-inf else -1

  复制代码
• 分割等和子集
  恰恰装capacity的方案数（变体，只要有一个就返回True）
  
  1. class Solution:
  2.     def canPartition(self, nums: List[int]) -> bool:
  3.         n = len(nums)
  4.         s = sum(nums)
  5.         if s%2: return False
  6.         target = s/2
  7.         @cache
  8.         def dfs(i,c):
  9.             if i<0:
  10.                 return c==0
  11.             if c<nums[i]:
  12.                 return dfs(i-1,c)
  13.             return dfs(i-1,c) or dfs(i-1,c-nums[i])
  14.         return dfs(n-1,target)
  15.         

  复制代码

完全背包

有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的最小代价和
  1. class Solution:
  2.     def coinChange(self, coins: List[int], amount: int) -> int:
  3.         # 硬币的面值 表示容量 然后硬币数量 每次选的话 就是1 相当于结果数
  4.         n = len(coins)
  5.         @cache
  6.         def dfs(i,c):
  7.             if i<0:
  8.                 return 0 if c==0 else inf
  9.             if c<coins[i]:
  10.                 return dfs(i-1,c)
  11.             return min(dfs(i-1,c),dfs(i,c-coins[i])+1)
  12.         res = dfs(n-1,amount)
  13.         return res if res<inf else -1
  14.         

  复制代码