唯品会一家做特卖的网站,廊坊网站建设技术支持,网页搜索怎么设置,电商最重要的四个岗位本文内容参考了代码随想录#xff0c;并进行了自己的总结。 完全背包
关键点
● 每件物品有若干种状态#xff1a;不选、选 1 件、选 2 件、…、选 n 件
代码
在代码上#xff0c;只有重量的遍历方向和 01 背包不一样#xff1a;
for(int i 0; i nums.length; i… 本文内容参考了代码随想录并进行了自己的总结。 完全背包
关键点
● 每件物品有若干种状态不选、选 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?pid1067完全背包恰好装满求排列方案数从[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所以物品的大小体积就是数值大小。物品价值这一题没有价值这个维度只是问背包装满是否存在方案。物品数量每个字符串可以选无数次。
单词拆分其实是的377. 组合总和 Ⅳ的子问题。
相同点
每个字符串相当于每个数字都是物品每个字符串的长度相当于每个数字的数值大小都是物品的大小
不同点 单词拆分问题问的是是否存在一种特定的排列能装满背包这个特定的排列装满背包就是指按照顺序拼接字符串。而给定的字符串 s 就表明了字符串一定要按照这个顺序拼接 组合总和 Ⅳ问题问的是能装满背包有多少种不同的排列方案即任意一种放入的顺序都算一种方案
