本文主要是介绍动态规划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])
- 当前 j 对应的最大价值为
- 一维dp数组的初始化
- 全部初始化为0即可
- 遍历顺序
- 对于纯完全背包类问题,内外层for循环可以互相颠倒,但是二者的遍历顺序均是从前往后
- 无需打印
- 一维dp数组dp[j]
- 代码书写问题
- 无
- 动规五部曲
# 一维数组解法
# 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])
*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] = 1for 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]
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] = 1for 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]
这篇关于动态规划06 | ● 完全背包 ● *518. 零钱兑换 II ● 377. 组合总和 Ⅳ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!