广州市公需课在哪个网站可以做,定制平台,开发公司公司简介,河南省城乡与住房建设厅网站首页完全背包理论基础
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品都有无限个#xff08;也就是可以放入背包多次#xff09;#xff0c;求解将哪些物品装入背包里物品价值总和最大。 01背包内嵌的循环是从…完全背包理论基础
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。 01背包内嵌的循环是从大到小遍历为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的所以要从小到大去遍历 动规五部曲 1.确定dp数组的定义
在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
2.一维dp数组的递推公式
dp[j]为 容量为j的背包所背的最大价值那么如何推导dp[j]呢
dp[j]可以通过dp[j - weight[i]]推导出来dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。也就是容量为j的背包放入物品i了之后的价值即dp[j]
此时dp[j]有两个选择一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]即不放物品i一个是取dp[j - weight[i]] value[i]即放物品i指定是取最大的毕竟是求最大价值
3.一维dp数组如何初始化
dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。
dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。
4.一维dp数组遍历顺序
因为物品有无限个所以内层循环可以正序遍历重复放入。
再来看看两个嵌套for循环的顺序代码中是先遍历物品嵌套遍历背包容量那可不可以先遍历背包容量嵌套遍历物品呢
可以
在完全背包中对于一维dp数组来说其实两个for循环嵌套顺序是无所谓的因为两个for循环都是正序遍历物品有无数个先遍历物品与先遍历背包得到的结果是相同的所以遍历顺序可以改变。因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。 // 先遍历物品再遍历背包
for(int i 0; i weight.size(); i) { // 遍历物品for(int j weight[i]; j bagWeight ; j) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}
} // 先遍历背包再遍历物品
for(int j 0; j bagWeight; j) { // 遍历背包容量for(int i 0; i weight.size(); i) { // 遍历物品if (j - weight[i] 0) dp[j] max(dp[j], dp[j - weight[i]] value[i]);}
}
5.举例推导dp数组 52. 携带研究材料典型完全背包问题
在本题现有代码基础上中需要先遍历物品再遍历背包如果先遍历背包再遍历物品由于这个题目是在第一层循环内输入weight和value这样会导致多输入一组 数据dp数组的长度为背包容量加1方便取到dp[w]防止数组越界解决只有使用一次for循环weight和value数组长度为n来填充weight和value数组来存储数据再做操作即可(如下面第二段代码)。
代码
import java.util.*;
import java.lang.*;public class Main{public static void main (String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int w in.nextInt();int[] dp new int[w1];for (int i 0; i n; i) {int weight in.nextInt();int value in.nextInt();for (int j weight; j w; j)dp[j] Math.max(dp[j], dp[j-weight] value);}// for(int i 0 ; i w ; i){// int weight in.nextInt();// int value in.nextInt();// for(int j 0; j n; j){// if (j - weight[i] 0) dp[j] max(dp[j], dp[j - weight] value);// }// }System.out.println(dp[w]);}
} import java.util.*;
import java.lang.*;public class Main{public static void main (String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int w in.nextInt();int[] dp new int[w1];int [] weight new int [n];int [] value new int [n];for (int i 0; i n; i) {int weights in.nextInt();int values in.nextInt();weight[i] weights;value[i] values;}// for(int num : weight){// System.out.print(num,);// }// System.out.println();// for(int nums : value){// System.out.print(nums,);// }for(int i 0 ; i w ; i){for(int j 0; j n; j){if (i - weight[j] 0) dp[i] Math.max(dp[i], dp[i - weight[j]] value[j]);}}System.out.println(dp[w]);}
}
518. 零钱兑换 II
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
纯完全背包是凑成背包最大价值是多少而本题是要求凑成总金额的物品组合个数
组合不强调元素之间的顺序排列强调元素之间的顺序。 动规五步曲
1.确定dp数组以及下标的含义
dp[j]凑成总金额j的货币组合数为dp[j]
2.确定递推公式
dp[j] 就是所有的dp[j - coins[i]]考虑coins[i]的情况相加。
所以递推公式dp[j] dp[j - coins[i]];
只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。
例如dp[j]j 为5
已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包。已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
3.dp数组如何初始化
首先dp[0]一定要为1dp[0] 1是 递归公式的基础。如果dp[0] 0 的话后面所有推导出来的值都是0了。下标非0的dp[j]初始化为0这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]。
4.确定遍历顺序
纯完全背包求得装满背包的最大价值是多少和凑成总和的元素有没有顺序没关系即有顺序也行没有顺序也行
而本题要求凑成总和的组合数元素之间明确要求没有顺序。 外层for循环遍历物品钱币内层for遍历背包金钱总额的情况。组合
for (int i 0; i coins.size(); i) { // 遍历物品for (int j coins[i]; j amount; j) { // 遍历背包容量dp[j] dp[j - coins[i]];}
}
假设coins[0] 1coins[1] 5。
那么就是先把1加入计算然后再把5加入计算得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。 外层for循环遍历背包金钱总额内层for遍历物品钱币的情况。排列
for (int j 0; j amount; j) { // 遍历背包容量for (int i 0; i coins.size(); i) { // 遍历物品if (j - coins[i] 0) dp[j] dp[j - coins[i]];}
}
背包容量的每一个值都是经过 1 和 5 的计算包含了{1, 5} 和 {5, 1}两种情况。
5.举例推导dp数组 //先物品后背包 class Solution {public int change(int amount, int[] coins) {int n coins.length;int[] dp new int[amount 1];Arrays.fill(dp, 0);dp[0] 1;for (int i 0; i n; i) {for(int j coins[i]; jamount;j){dp[j] dp[j-coins[i]];}}return dp[amount];}} 377. 组合总和 Ⅳ
本题题目描述说是求组合但又说是可以元素相同顺序不同的组合算两个组合其实就是求排列 组合不强调顺序(1,5)和(5,1)是同一个组合。
排列强调顺序(1,5)和(5,1)是两个不同的排列。
动规五部曲
1.确定dp数组以及下标的含义
dp[i]: 凑成目标正整数为i的排列个数为dp[i]
2.确定递推公式
dp[i] dp[i - nums[j]];
3.dp数组如何初始化
因为递推公式dp[i] dp[i - nums[j]]的缘故dp[0]要初始化为1这样递归其他dp[i]的时候才会有数值基础。
至于dp[0] 1 有没有意义呢
其实没有意义所以我也不去强行解释它的意义了因为题目中也说了给定目标值是正整数 所以dp[0] 1是没有意义的仅仅是为了推导递推公式。
至于非0下标的dp[i]应该初始为多少呢
初始化为0这样才不会影响dp[i]累加所有的dp[i - nums[j]]。
4.确定遍历顺序
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
5.举例来推导dp数组 class Solution {public int combinationSum4(int[] nums, int target) {int[] dp new int[target 1];dp[0] 1;for (int i 0; i target; i) {for (int j 0; j nums.length; j) {if (i nums[j]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
} 二维解法
public class ALL {public static void main(String[] args) {int[] coins new int[]{1, 2, 5};int amount 5;int result change(5, coins);System.out.println(result);}public static int change(int amount, int[] coins) {int[][] dp new int[amount 1][coins.length1];dp[0][0] 1;// weight数组的大小 就是物品个数for (int i 1; i amount; i) { // 遍历背包容量for (int j 1; j coins.length; j) { // 遍历物品,统一下标if (coins[j - 1] i) { //保证背包容量比物品容量大for (int k 0; k coins.length; k) { //对列进行操作 找出满足某一个背包容量的“组合数”有多少dp[i][j] dp[i - coins[j-1]][k];}}}}int res 0;for (int i 0; i coins.length; i) { /最后对满足背包容量的所有组合加起来即为排列res dp[amount][i];}return res;}}
