学校网站模板代码,com都有哪些网站,德清建设银行官方网站,phpcms插件#Java #完全背包 #动态规划
Feeling and experiences#xff1a;
动态规划#xff1a;完全背包理论基础
之前学习的是01背包#xff0c;其特点在于#xff1a;每个物品都只能取一个
而完全背包则是可以一个物品取多个。
有N件物品和一个最…#Java #完全背包 #动态规划
Feeling and experiences
动态规划完全背包理论基础
之前学习的是01背包其特点在于每个物品都只能取一个
而完全背包则是可以一个物品取多个。
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。 零钱兑换II力扣题目链接
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。 示例 1
输入amount 5, coins [1, 2, 5]
输出4
解释有四种方式可以凑成总金额
55
5221
52111
511111该题理解递推公式
dp[j] dp[j-coins[i]];
• 外循环遍历每一种硬币。 • 内循环从该硬币面值开始直到目标金额。 • 更新dp[j]的值对于每个jdp[j]增加dp[j - coins[i]]的值。这表示如果你已经知道了组成金额j - coins[i]的方法数那么只需加上当前硬币coins[i]就可以组成金额j。
注意这里 内外 循环的区别
class Solution {public int change(int amount, int[] coins) {//因为硬币的数量可以随意取//这是一个完全背包问题//创建dp数组 dp数组的含义装满容量为 j 的背包 有dp[j]种方法int []dp new int[amount1];//怎么递推出来的//dp[j] dp[j - coins[i]]; //初始化dp数组dp[0] 1; //这里要初始化为1 不然后面递推不了了 for(int i 0;i coins.length;i){for(int j coins[i];jamount;j){dp[j] dp[j-coins[i]];}}return dp[amount];}
}
乍一看和01背包问题很像
以下是硬币只能取一次的代码
class Solution {public int change(int amount, int[] coins) {int[] dp new int[amount 1];dp[0] 1;for (int i 0; i coins.length; i) {for (int j amount; j coins[i]; j--) {dp[j] dp[j - coins[i]];}}return dp[amount];}
}
这里的关键变化是内循环的遍历方向。
由于每种硬币只能使用一次所以我们必须从后向前更新 dp 数组。这样当计算 dp[j] 时dp[j - coins[i]] 还没有被当前的硬币影响确保了每种硬币只被使用一次。 组合总和 Ⅳ力扣题目链接
给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。 示例 1
输入nums [1,2,3], target 4
输出7
解释
所有可能的组合为
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意顺序不同的序列被视作不同的组合。这道题就相当于是 零钱兑换II 求组合 变成了求排列
class Solution {public int combinationSum4(int[] nums, int target) {//关键不同 序列被视作 不同组合//创建dp数组 含义 得到target 有dp[target]种方法int []dp new int[target1];//递推公式//dp[i] dp[i-nums[j]];//初始化dp数组dp[0] 1;for(int i 0;itarget;i){for(int j 0;jnums.length;j){if(i nums[j]){dp[i] dp[i-nums[j]];}}}return dp[target];}
}
比如【13】 【31】 算两种不同的结果滟滟随波千万里
何处春江无月明
Fighting
