广东华迪工程建设监理公司网站,wordpress 提示-1,汉源网站建设,网站模板 帝国 phpcms完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品都有无限个#xff08;也就是可以放入背包多次#xff09;#xff0c;求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同…完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。
同样leetcode上没有纯完全背包问题都是需要完全背包的各种应用需要转化成完全背包问题所以我这里还是以纯完全背包问题进行讲解理论和原理。
每件物品可以放入多次
为什么遍历物品在外层循环遍历背包容量在内层循环 01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了一维dp数组的两个for循环先后循序一定是先遍历物品再遍历背包容量。
在完全背包中对于一维dp数组来说其实两个for循环嵌套顺序是无所谓的
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。 518.零钱兑换II(两次)
力扣题目链接(opens new window)
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount 5, coins [1, 2, 5]输出: 4
解释: 有四种方式可以凑成总金额:
55522152111511111
看到题目的第一想法 确定可以凑成dp的组合数 但是相同面额的可以重复使用完全背包
看到代码随想录之后的想法 确定dp数组以及每个下标的含义 dp[j] 为0~i之间能凑成j金额所需要的次数 i为coins下标 确定递推公式 选中coins[i] 则一共有j-coins[i]种能凑成j 再加上本身的dp[j] 就知道添加了coins[i]后一共要多少次 dp[j] dp[j] dp[j-coins[i]] 确定遍历顺序 可以重复添加物品则从前往后 dp数组初始化 dp[0]1为一切的源头其他都为0 举例推导dp数组 自己实现过程中遇到的困难 我自己写成了 max(dp[j]dp[j-weight[i]]1) 记混了 要理解组合数求的是能凑成j的数目需要累加j-coins[i]
class Solution {public int change(int amount, int[] coins) {//有多少种方式可以凑成对应面额// 确定dp数组以及每个下标的的含义// 能凑成目标金额的最大个数// 确定递推公式// dp[i]dp[i-nums[i]]// dp数组初始化// dp[0]1;其他都为0// 确定遍历顺序// 从前往后因为可以重复// 手动推导dp数组// 打印dp数组int dp[] new int[amount1];dp[0]1;for(int i0;icoins.length;i){//从前往后for(int jcoins[i];jamount;j){dp[j]dp[j]dp[j-coins[i]];}}return dp[amount];}
}
377. 组合总和 Ⅳ
力扣题目链接(opens new window)
难度中等
给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的组合的个数。
示例:
nums [1, 2, 3]target 4
所有可能的组合为 (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意顺序不同的序列被视作不同的组合。
因此输出为 7。
看到题目的第一想法 可以凑成目标正整数的组合的个数。 和零钱兑换II差不多
看到代码随想录之后的想法 确定dp数组以及每个下标的含义 dp[j] 为0~i之间能凑成target所需要的次数 i为nums下标 确定递推公式 选中nums[i] 则一共有j-nums[i]种能凑成j 再加上本身的dp[j] 就知道添加了nums[i]后一共要多少次 dp[j] dp[j] dp[j-nums[i]] 确定遍历顺序 可以重复添加物品则从前往后 比如说 (1231) 若可以凑成target 如果先物品后背包 物品1 遍历完后 将再也不会遍历到1之后遍历的是物品234 所以必须先背包后物品 外层循环是背包容量物品按照 1 2 3 4的顺序依次遍历 则 遍历完1,2,3还能遍历回1 dp数组初始化 dp[0]1为一切的源头其他都为0 举例推导dp数组 自己实现过程中遇到的困难 需要确认组合数和排列数的区别(看代码注释) 组合数 不强调顺序不同顺序的都视为一个集合必须先物品再背包 排列数 本题不同的地方在于不同顺序的视为不同集合则必须先背包再物品
class Solution {public int combinationSum4(int[] nums, int target) {// 组合数先遍历物品再遍历背包每次选中一个物品都会遍历所有背包 1号物品一定在2号物品的前面// 排列数先遍历背包再遍历物品则每次选中一个背包都会遍历所有物品 每次都是 1号物品2号物品。。。。 // 第二次 1号物品2号物品 1 2 交替 // 确定dp数组以及对应下标的含义// 在0~i中满足总和为j的元素的个数,背包重量nums[i] 背包价值nums[i]// 确定递推公式// dp[j]dp[j-nums[i]]// dp数组的初始化// dp[0]1 // 确定遍历顺序// 可以重复 从前往后// 组合数 不强调顺序不同顺序的都视为一个集合必须先物品再背包// 排列数 本题不同的地方在于不同顺序的视为不同集合则必须先背包再物品// 手动推导dp数组int[] dp new int[target1];dp[0]1;for(int j0;jtarget;j){for(int i0;inums.length;i){if(jnums[i]){dp[j]dp[j-nums[i]];}}}return dp[target];}
}
