【2025力扣打卡系列】0-1背包 完全背包

坚持按题型打卡&刷&梳理力扣算法题系列，语言为python3，Day5

• 0-1背包【目标和】
  • 有n个物品，第i个物品的体积为w[i], 价值为v[i]。每个物品至多选一个，求体积和不超过capacity时的最大价值和
  • 常见变形
    • 至多装capacity，求方案数/最大价值和（max）
    • 恰好装capacity，求方案数/最大/最小价值和（+）
    • 至少装capacity，求方案数/最小价值和（min）
• 完全背包【零钱兑换】
  • 有 n 种物品，第 i 种物品的体积为w[i], 价值为v[i]。每种物品无限次重复选，求体积和不超过capacity时的最大价值和
  • 🌟与0-1背包回溯的区别：
    • 在选了一个物品之后，i 是不变的，表示可以继续选第 i 种物品

目标和

• 题目描述
  
• 代码参考

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:target += sum(nums)if target < 0 or target % 2:return 0target //= 2 # //和等号之间不能留空格n = len(nums)@cachedef dfs(i,c):if i < 0: # 当前的物品取完了return 1 if c==0 else 0 # 判断结果是否合法if c < nums[i]: # 勿漏！！如果当前剩余容量c小于nums[i], 则直接return 不选return dfs(i-1,c)return dfs(i-1,c) + dfs(i-1,c-nums[i]) # 否则return两者（不选 选）相加return dfs(n-1,target)

零钱兑换

• 题目描述

• Tips

  • 首先拿到数组长度
  • 然后定义dfs函数
    • 先写边界条件，注意判断合法情况
    • 再判断c（背包容量）够不够减，不够的话就直接return不选
    • return max/+/min 不选 选

• 代码参考

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)@cachedef dfs(i,c): #此处dfs返回值代表的是硬币个数if i < 0:return 0 if c==0 else inf # 当所有种类物品取完的时候，判断是否合法，inf代表无穷大if c < coins[i]:return dfs(i-1,c)return min(dfs(i-1,c),dfs(i,c-coins[i])+1)ans = dfs(n-1,amount)return ans if ans < inf else -1