完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

题干解析

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 bag 比如:

1
2
3

weight = [1, 3, 4]  // 三个物品
value = [15, 20, 30] // 对应该的价值
bagweight = 4 // 背包的容量为4

问背包能背的物品最大价值是多少？

01背包和完全背包唯一不同就是体现在遍历顺序上，我们直接分析。

首先再回顾一下01背包的核心代码:

1
2
3
4
5
6
7

for i := 0; i < n; i++ { //遍历物品
	// 需要注意的是，j 一定要从大到小，防止物品0 被重复计算
	for j := bagWeight; j >= weight[i]; j-- { //遍历背包容量
		dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
	}

}

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

1
2
3
4
5
6
7


for i :=0; i < n; i ++ {	//遍历物品
	// 完全背包，i 可以重复添加，要从小到大遍历
	for j := weight[i]; j <= bagWeight; j ++ {
		dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
	}
}

其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？ 难道就不能遍历背包容量在外层，遍历物品在内层？ 01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。 在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！ 因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

应用

讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

背包总结

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); 对应题目如下：
416.分割等和子集
1049.最后一块石头的重量 II

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
494.目标和
518.零钱兑换II
377. 组合总和 Ⅳ
70. 爬楼梯

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 对应题目如下：
474.一和零

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); 对应题目如下：
322. 零钱兑换
279. 完全平方数