动态规划06 | ● 完全背包 ● *518. 零钱兑换 II ● 377. 组合总和 Ⅳ

完全背包

视频讲解：https://www.bilibili.com/video/BV1uK411o7c9
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html

• 题目描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品可以重复使用，求解怎么装背包里物品价值总和最大。
• 解法大体和01背包的解法相同，以下以一维数组解法为例，其和01背包的解法主要有两点不同：
  • 一是内层for循环从逆向遍历改为正向遍历，因为完全背包里的每个物品是可以多次放入背包中的
  • 二是对于纯完全背包问题，内外层for循环是可以颠倒的，也就是说先遍历物品和先遍历背包容量都可以，其中为什么先遍历背包容量也可以呢？这样不会导致过程中某些dp[j]依赖于了下一个物品的dp[j]吗？其实是没关系的，无论是否依赖了下一个物品，我们最终得到的最后的那个结果值都不会变，也就是说过程中即便发生了变化，结果仍然是正确的。但从理论上来讲，其实还是应该先遍历物品，这样每一步都是正确的，不会产生困惑
    • 而对于完全背包应用类题目里的求装满背包有多少种情况的问题，内外层循环的顺序有如下讲究
      • 先遍历物品，再遍历背包容量，得到的结果是组合数——因为此时在不同种背包容量的情况里，都是先放进物品1再放进物品2，不会出现先放2再放1的情况，此时得到的组合之间不会出现顺序不同、元素相同的情况
      • 先遍历背包容量，再遍历物品，得到的结果是排列数——因为此时在背包容量递增的过程中，物品1和物品2放入的先后顺序不一定，可能先放了1也可能先放了2，因此集合之间会出现顺序不同、元素相同的情况，也就是得到的结果是排列数
• 滚动数组（一维数组解法）
  • 动规五部曲
    • 一维dp数组dp[j]
      • 其中j代表背包的容量，dp值代表对应的最大价值
    • 递推公式
      • 当前 j 对应的最大价值为 装第i个物品 和 不装第i个物品 两种情况里的较大值
      • 其中装第i个物品对应的dp值为dp[j - weight[i]] + value[i]，weight[i]表示第i个物品的重量，value[i]代表第i个物品的价值
      • 不装第i个物品对应的dp值为dp[j]
      • 即dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    • 一维dp数组的初始化
      • 全部初始化为0即可
    • 遍历顺序
      • 对于纯完全背包类问题，内外层for循环可以互相颠倒，但是二者的遍历顺序均是从前往后
    • 无需打印
  • 代码书写问题
    • 无

# 一维数组解法
# m种物品，背包容量为n，每个物品的重量和价值分别保存在weight和value里
dp = [0] * (n + 1)
for i in range(1, m):
    for j in range(1, n + 1):
        if (j - weight[i]) >= 0:
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp[-1])
1
2
3
4
5
6
7
8

*518. 零钱兑换 II

视频讲解：https://www.bilibili.com/video/BV1KM411k75j
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html

• 考点
  • 动态规划
  • 完全背包
  • 组合和排列（下一道题就是排列问题）
• 我的思路
  • 思路就是给一个背包和给多个物品，问装满背包有多少种组合（每个物品可以重复拿取）
• 视频讲解关键点总结
  • 我的思路没有问题，需要注意的是，不同的内外循环顺序会带来不同的结果，一种计算的是组合数，一种计算的是排列数（相同的元素，不同的顺序也视为不同）
    • 先遍历物品，再遍历背包容量，得到的结果是组合数——因为此时在不同种背包容量的情况里，都是先放进物品1再放进物品2，不会出现先放2再放1的情况，此时得到的组合之间不会出现顺序不同、元素相同的情况
    • 先遍历背包容量，再遍历物品，得到的结果是排列数——因为此时在背包容量递增的过程中，物品1和物品2放入的先后顺序不一定，可能先放了1也可能先放了2，因此集合之间会出现顺序不同、元素相同的情况，也就是得到的结果是排列数
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(1, amount + 1):
                if j >= coins[i]:
                    dp[j] += dp[j - coins[i]]
        return dp[-1]
1
2
3
4
5
6
7
8
9

377. 组合总和 Ⅳ

视频讲解：https://www.bilibili.com/video/BV1V14y1n7B6
https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html

• 考点
  • 动态规划
  • 完全背包
  • 组合和排列
• 我的思路
  • 思路就是给一个背包和给多个物品，问装满背包有多少种排列（每个物品可以重复拿取）
• 视频讲解关键点总结
  • 我的思路没有问题，需要注意的是，不同的内外循环顺序会带来不同的结果，一种计算的是组合数，一种计算的是排列数（相同的元素，不同的顺序也视为不同）
    • 先遍历物品，再遍历背包容量，得到的结果是组合数——因为此时在不同种背包容量的情况里，都是先放进物品1再放进物品2，不会出现先放2再放1的情况，此时得到的组合之间不会出现顺序不同、元素相同的情况
    • 先遍历背包容量，再遍历物品，得到的结果是排列数——因为此时在背包容量递增的过程中，物品1和物品2放入的先后顺序不一定，可能先放了1也可能先放了2，因此集合之间会出现顺序不同、元素相同的情况，也就是得到的结果是排列数
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for j in range(1, target + 1):
            for i in range(len(nums)):
                if j >= nums[i]:
                    dp[j] += dp[j - nums[i]]
        return dp[-1]
1
2
3
4
5
6
7
8
9