完全背包理论基础
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
首先再回顾一下01背包的核心代码：
for i in range(len(weight)): // 遍历物品
for j in(bagWeight, weight[i], -1): // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：
// 先遍历物品，再遍历背包
for i in range(len(weight)): // 遍历物品
for j in range(weight[i], bagWeight) // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])Python代码如下：
// 先物品，后背包
def test_CompletePack():
weight = [1, 3, 4]
value = [15, 20, 30]
bagWeight = 4
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(weight[i], bagWeight + 1): # 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp[bagWeight])// 先背包，后物品
def test_CompletePack():
weight = [1, 3, 4]
value = [15, 20, 30]
bagWeight = 4
dp = [0] * (bagWeight + 1)
for j in range(bagWeight + 1): # 遍历背包容量
for i in range(len(weight)): # 遍历物品
if j - weight[i] >= 0:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp[bagWeight])518.零钱兑换Ⅱ
动规五部曲：
1.dp数组及其下标含义：dp[j]表示当前的货币共有dp[j]种组合方式可以组成总金额j；
2.确定递推公式：dp[j]就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。本题也属于求装满背包有几种方法，所以公式为：dp[j] += dp[j - coins[i]]；
3.dp数组初始化：由于dp数组中后面的值是由前面的值计算得出的，所以dp[0]必须要初始化为1，下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]；
4.确定遍历顺序：先物品后背包，不可用先背包后物品，否则计算出来的不是组合数而是排列数；
5.打印dp数组
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(coins[i], amount + 1):
dp[j] += dp[j - coins[i]]
return dp[-1]377.组合总和Ⅳ
本题的思路与前一题基本一致，因为每个数字可使用的次数不限，所以同属完全背包问题。区别在于本题求的是组合总数，而不是排列数，因此在遍历顺序上要做出调整。因为先物品后背包求的是排列数，所以要先背包后物品求得才是组合数。
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for j in range(len(nums)):
if i - nums[j] >= 0:
dp[i] += dp[i - nums[j]] # 求装满背包有多少种方法用的都是这个公式
return dp[-1]
