一、问题介绍与解题心得

完全背包问题与01背包问题很相似，不同点就是每个物品数量有多个，每个物品可以取多个或不取，来达到收益最大，或者收益在某个值。

限制条件：背包容量有限

解决问题：从价值入手（价值最大或是某个值），从容量入手（不超过最大体积还是刚好装到某一个体积）

设的 dp 表一般是 dp[i][j] 表示在 [1, i] 的物品中选择，符合要求 j 的价值

此处以完全背包模板题为例：【模板】完全背包_牛客题霸_牛客网

1、传统方法

这里根据要求的不同用两个 dp 表解决问题，分析过程不赘述，主要看总结的规律。

由于完全背包中物品个数有多个，所以不选 i 物品是去看 dp[i - 1] 位置的值，选 i 物品是去看 dp[i] 位置的值，所以要进行空间优化的话就是用 dp[i - 1][j] 和 dp[i][j - v[i]] 来更新 dp[i] 的值，而我们现在只有一个一维数组，已知我们要更新的 dp[i][j] 是需要旧的一维数组表中的正上方 dp[i - 1][j] 和新的数组表中的相对于 j 位置之前的值 dp[i][j - v[i]]，所以dp[i] 的更新一定是从前向后的更新。

所以总结，完全背包问题的空间优化是删去行元素，从前向后更新。

2、空间优化

二、例题

1、零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

2、零钱兑换2

518. 零钱兑换 II - 力扣（LeetCode）

3、完全平方数

279. 完全平方数 - 力扣（LeetCode）

三、总结

其实完全背包问题就是要你把问题转化成在一段不重复的数据里面取出任意个数据满足条件。