【leetcode】完全背包总结

本文内容参考了代码随想录，并进行了自己的总结。

完全背包

关键点

● 每件物品有若干种状态：不选、选 1 件、选 2 件、…、选 n 件

代码

在代码上，只有重量的遍历方向和 01 背包不一样：

for(int i = 0; i < nums.length; i ++ )for(int j = nums[i]; j <= W; j ++ ) {dp[j] = Math.max(dp[j], dp[j - nums[i]);}

正序遍历，意味着每件物品可以选多次，一直往后叠加。

题目

问能装的最大容量，或者问能不能装满的这种题目，属性既是重量又是价值。

下面是代码随想录中，完全背包问题的总结。

题目	问题转换	属性拆解
518. 零钱兑换 II 完全背包 恰好装满，求组合方案数 备注： 组合方案数，就是装的数的顺序不影响结果。比如 3 = 1 + 2 和 3 = 2 + 1 是同一种方案	给定背包容量amount，从coins中选若干个物品放入背包，问能装满的组合方案数	背包容量：amount。 物品体积：由于是选若干个硬币出来让他们的金额和等于 amount，所以物品的大小（体积）就是硬币金额。 物品价值：这一题没有价值这个维度，只是问背包装满的方案数。 物品数量：每个硬币可以选无数次。
377. 组合总和 Ⅳ 完全背包 恰好装满，求排列方案数	从nums中选若干个数，每个数可重复选择，放入容量为 target的背包，问放满的排列方案数。	背包容量：target。 物品体积：由于是选若干个数字出来让他们的和等于 target，所以物品的大小（体积）就是数值大小。 物品价值：这一题没有价值这个维度，只是问背包装满的方案数。 物品数量：每个数字可以选无数次。
https://kamacoder.com/problempage.php?pid=1067 完全背包 恰好装满，求排列方案数	从[1, m]中，选若干个数，每个数可选无数次，放入大小为n的背包，问放满的排列方案数	背包容量：n。 物品体积：由于是选若干个数字出来让他们的和等于 n，所以物品的大小（体积）就是数值大小。 物品价值：这一题没有价值这个维度，只是问背包装满的方案数。 物品数量：每个数字可以选无数次。
322. 零钱兑换 完全背包 恰好装满，求最小价值	给定n个数，选若干个数，每个数无限取，求能放满背包的最少数的个数。 给定n个数，选若干个数，每个数无限取，求恰好装满时，最小价值为多少？	背包容量：n。 物品体积：由于是选若干个数字出来让他们的和等于 n，所以物品的大小（体积）就是数值大小。 由于是求最少数的个数，所以每个数的价值就是 1。 物品数量：每个数字可以选无数次。
279. 完全平方数 完全背包 恰好装满，求最小价值	从[1, sqrt(n)]中选若干个数，每个数可选无数次，将其平方放入大小为n的背包中，求能放满的最少数量 从[1, sqrt(n)]中选若干个数，每个数可选无数次，将其平方放入大小为n的背包中，求恰好装满时，最小价值为多少？	背包容量：n。 物品体积：由于是选若干个数字出来让他们平方的和等于 n，所以物品的大小（体积）就是数值大小。 物品价值：由于是求最少数的个数，所以每个数的价值就是 1 物品数量：每个数字可以选无数次。
139. 单词拆分 完全背包 按顺序恰好装满，求是否存在方案	从n个字符串中选若干个字符串，每个字符串可重复使用，拼成长度为s.length()的字符串，问是否能拼成？ 从n个物品中选若干个物品，每个物品可重复使用，放入大小为s.length()的背包，问是否能装满？ 这n个物品是有顺序的，即必须按照一定的顺序拼成字符串s，所以求的是是否存在一种排列能够拼成字符串s，所以遍历顺序应该先遍历长度	背包容量：s.length()。 物品体积：由于是选若干个字符串出来让他们的长度等于 n，所以物品的大小（体积）就是数值大小。 物品价值：这一题没有价值这个维度，只是问背包装满是否存在方案。 物品数量：每个字符串可以选无数次。

139. 单词拆分其实是的377. 组合总和 Ⅳ的子问题。

相同点：

• 每个字符串相当于每个数字，都是物品
• 每个字符串的长度相当于每个数字的数值大小，都是物品的大小

不同点：

• 139. 单词拆分问题问的是，是否存在一种特定的排列能装满背包？这个特定的排列装满背包，就是指按照顺序拼接字符串。而给定的字符串 s 就表明了，字符串一定要按照这个顺序拼接
• 377. 组合总和 Ⅳ问题问的是，能装满背包有多少种不同的排列方案，即任意一种放入的顺序都算一种方案