[完全背包]
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
1、先遍历物品再遍历背包
def all_bag(weight, value, bag_weight):
dp = [0] * (bag_weight + 1)
for i in range(len(weight)): # 先遍历物品
for j in range(weight[i], bag_weight + 1): # 再遍历背包
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(f'物品重量为: {weight[i]}, 背包可背的重量为: {j}, 背包dp[{j}]最大价值为: {dp[j]}')
print(dp)
return dp[bag_weight]
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
res = all_bag(weight, value, bag_weight)
print(res)
2、先遍历背包后遍历物品
def all_bag(weight, value, bag_weight):
dp = [0] * (bag_weight + 1)
for i in range(bag_weight + 1): # 先遍历背包
for j in range(len(weight)): # 再遍历物品
if i >= weight[j]:
dp[i] = max(dp[i], dp[i - weight[j]] + value[j])
print(f'背包可背的重量为: {i}, 物品重量为: {weight[j]}, 背包dp[{i}]最大价值为: {dp[i]}')
print(dp)
return dp[bag_weight]
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
res = all_bag(weight, value, bag_weight)
print(res)
总结: 先背包后物品排列，先物品后背包组合
518. 零钱兑换 II
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# dp 数组代表金额为 j 的组合总数为 dp[j]
dp = [0] * (amount + 1)
# 初始化数组为 1
dp[0] = 1
# 先遍历物品再遍历背包是组合
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# dp 数组代表 target 为 j 时的组合个数为 dp[j]
dp = [0] * (target + 1)
dp[0] = 1
# 求排列先遍历背包后遍历物品
for i in range(target + 1):
for num in nums:
if i >= num:
dp[i] += dp[i-num]
return dp[target]