代码随想训练营第四十四天（Python）｜ 完全背包、518. 零钱兑换 II 、377. 组合总和 Ⅳ

[完全背包]
有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]

377. 组合总和 Ⅳ

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]