完全背包理论部分
- 问题雏形：
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。 - 重点
与01背包的区别在于递归顺序
结论：
（1）01背包中二维dp数组的两个for遍历的先后循序可以颠倒，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
（2）在完全背包中，对于一维dp数组，两个for遍历的先后循序可以颠倒。 - 完全背包的遍历顺序理解：
dp[j] 是根据下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。从二维图形理解：
（1）外层物品，内层背包，则在逐步物品选择下：
step1：得到只用物品0在不同容量的最大价值
step2：在更新dp[j] (j = 0…n)之后，考虑物品0、1下不同背包容量的最大价值，按照递推公式dp[j] = max(dp[j], dp[j - value[i]]+value[i]) 来看，dp[j] 和 dp[j - value[i]]应该是更新过的左上角的值
讯享网
（2）外层背包，内层物品，同理分析：
518. 零钱兑换 II
class Solution: def change(self, amount: int, coins: List[int]) -> int: # dp[i]表示面额为i的硬币组合数，即装满背包的组合的完全背包类型 total_sum = sum(coins) dp = [0] * (amount + 1) dp[0] = 1 for u in coins: for j in range(u, amount+1): # 注意遍历顺序，是在所有考虑的背包容量下逐步将物品加入，所以不会出现排列的重复情况，而是组合形式 dp[j] += dp[j - u] return dp[amount] 讯享网
377. 组合总和 Ⅳ
讯享网class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0] * (target + 1) dp[0] = 1 for j in range(target+1): for u in nums: if u <= j: dp[j] += dp[j - u] return dp[target]
总结
在求装满背包的组合个数时：
（1）递归公式都是：dp[j] += dp[j - value[i]]
（2）遍历顺序的选择：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
这个可以结合完全背包解释遍历顺序的原因去理解，求组合数时，如果外层背包+内层物品，则在给定背包容量下，不同的物品的组合个数已经进行更新，即可以选择不同的物品，变更背包容量，则会发生{1, 5}和{5，1}这种重复选择。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/116049.html