精准网站seo诊断报告,常见的线下推广渠道有哪些,logo设计公司免费,网站icon怎么做的文章目录 背包问题动规五部曲一、0-1背包问题 #xff1a;限制物品不可重复 (要么不选 要么选一个)二、完全背包问题#xff1a;不限制重复#xff08;要么不选 要么可以多选#xff09;#xff08;完全背包可以转化为0-1背包问题#xff09; 动态规划#xff1a;01背包… 文章目录 背包问题动规五部曲一、0-1背包问题 限制物品不可重复 (要么不选 要么选一个)二、完全背包问题不限制重复要么不选 要么可以多选完全背包可以转化为0-1背包问题 动态规划01背包 二维dp数组动态规划01背包滚动数组动规五部曲分析如下动态规划代码 背包问题 动规五部曲
其中最主要的就是前两个步骤
确定dp数组以及下标的含义确定递推公式dp数组如何初始化遍历顺序出结论写代码
一、0-1背包问题 限制物品不可重复 (要么不选 要么选一个)
二、完全背包问题不限制重复要么不选 要么可以多选完全背包可以转化为0-1背包问题
下面讲的是0-1背包问题 其中
i,表示物品j表示背包容量w[] 数组表示物品重量的集合v[] 数组表示物品价值的集合v[][]表示装入背包的最大价值集合
1找w[i]和j的关系 v[i][0]v[0][j]0,表示第一列和第一行最大价值都是0 1.w[i]j,表示当前准备新增物品的质量要是大于背包的容量v[i][j] v[i-1][j]该位置的最大价值就是把该列上一行的数据赋给它如第二次音响进来的最大价值情况v[i-1][j]上一个单元格装入的最大价值2.jw[i]表示背包的容量要是大于等于当前要新增物品的质量 (2) 则装入的最大价值策略为v[i][j] max { v[i-1][j], v[i] v[i-1][j-w[i]] } v[i] 当前商品的价值 j-w[i] 装入当前物品后背包剩余的容量大小
(3) v[i] v[i-1][j-w[i]]表示装入当前物品的价值 剩余容量可装入的最大价值 最后比较 两个最大价值取max eg总w4电脑w3装入后的价值2000 剩余w1只可装一个吉他价值15003500 上一个单元格装入的最大价值3000 所以选择这个装配方式 上面讲的很清楚了 看一下具体的实现
那么可以有两个方向推出来dp[i][j] 1.不放物品idp[i][j]dp[i - 1][j]。 w[i]j表示当前准备新增物品的质量要是大于背包的容量v[i][j] v[i-1][j] 就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以被背包内的价值依然和前面相同。 2.放物品i 表示背包的容量要是大于等于当前要新增物品的质量 dp[i - 1][j - weight[i]]推出 dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候 不放物品i所以是i-1的最大价值value[i]dp[i - 1][j - weight[i]] 表示装入当前物品的价值 剩余容量可装入的最大价值 所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
动态规划01背包 二维dp数组
动规五部曲分析一波。
确定dp数组以及下标的含义
- 对于背包问题有一种写法 是使用二维数组即dp[i][j] 表示从下标为[0,i]的物品里任意取放进容量为j的背包价值总和最大是多少。
- w[i] 表示第i个物品的重量
- v[i] 表示第i个物品的价值要时刻记着这个dp数组的含义下面的一些步骤都围绕这dp数组的含义进行的如果哪里看懵了就来回顾一下i代表什么j又代表什么。
确定递推公式
再回顾一下dp [i][j]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。# 那么可以有两个方向推出来dp[i][j]
##1.不放物品idp[i][j]dp[i - 1][j]。
------w[i]j,表示当前准备新增物品的质量要是大于背包的容量v[i][j] v[i-1][j]就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以被背包内的价值依然和前面相同。
##2.放物品i表示背包的容量要是大于等于当前要新增物品的质量# dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候 不放物品i所以是i-1的最大价值# value[i]dp[i - 1][j - weight[i]] 表示装入当前物品的价值 剩余容量可装入的最大价值所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);动态规划01背包滚动数组
读到这里估计大家都忘了 dp[i][j]里的i和j表达的是什么了i是物品j是背包容量。
dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
动规五部曲分析如下 确定dp数组的定义 在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。 一维dp数组的递推公式
dp[j]可以通过dp[j - weight[i]]推导出来 dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。 dp[j - weight[i]] value[i] 表示容量为 j-物品i重量的背包的价值 加上 物品i的价值。 就是容量为j的背包放入物品i了之后的价值再加上物品i的价值此时dp[j]有两个选择 一个是取自己dp[j] 相当于二维dp数组中的dp[i-1][j]即不放物品i 一个是取dp[j - weight[i]] value[i]即放物品i指定是取最大的毕竟是求最大价值所以递归公式为 dp[j] max(dp[j], dp[j - weight[i]] value[i]);
一维dp数组如何初始化 dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么背包容量为0所背的物品的最大价值就是0。
所以dp[0]0
假设物品价值都是大于0的所以dp数组初始化的时候都初始为0就可以了。
Arrays.fill(dp,0);遍历顺序从后向前
还是先遍历物品然后再遍历背包容量
for(int i 0; i v.length; i) { // 遍历物品for(int j weight; j w[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - w[i]] v[i]);}
}动态规划代码
代码
public static void main(String[] args) {int[] v {15, 20, 30};int[] w {1, 3, 4};int weight 4;int[] dp new int[weight 1];Arrays.fill(dp, 0);//i是物品 j是背包重量 所以物品重量是w[i]int resdp[0];for (int i 0; i v.length; i) {for (int j weight; j w[i]; j--) {dp[j]Math.max(dp[j],dp[j-w[i]]v[i]);resMath.max(res,dp[j]);}}System.out.println(res);}public static void main(String[] args) {int[] value new int[]{1500, 2000, 3000};//表示物品的价值int[] weight {1, 4, 3};//表示物品的重量int w 4;//背包的容量int n value.length;//物品的个数//创建一个二维数组 表 n1行有一行是0行w1列有一列是0列int[][] dp new int[n 1][w 1]; //n1就是列长 w1就是行长//1.初始化第一行第一列for (int i 0; i w 1; i) {dp[0][i] 0;//第一行为0}for (int i 0; i n 1; i) {dp[i][0] 0;//第一列为0}int resdp[0][0];//2.判断物品重量w[i] 和背包容量的关系for (int i 1; i dp.length; i) {//从第一行for (int j 1; j dp[0].length; j) {//第一列开始if (weight[i-1] j) {//i-1是因为我们从1开始的dp[i][j] dp[i - 1][j];} else {dp[i][j] Math.max(dp[i - 1][j], (value[i-1] dp[i - 1][j - weight[i-1]]));//value[i-1] //是因为我们的i是从1开始的 所以-1//weight[i-1]}resMath.max(res,dp[i][j]);}}
// 3.打印这个最大价值表for (int i 0; i dp.length ; i) {for (int j 0; j dp[0].length; j) {System.out.print(dp[i][j]\t);}System.out.println();}System.out.println(最大价值为res);}
}
