网站没有权重,wordpress 改 分隔,北京二手房网站,爱分享wordpress背包问题#xff08;贪心#xff09;
最优装载问题
题目描述
有n件物品和一个最大承重为w 的背包。第i件物品的重量是weight[i]#xff0c;每件只能用一次#xff0c;求装入背包的最多物品数量。
题目分析
因为我们只要求装入物品的数量#xff0c;所以装重的显然没有…背包问题贪心
最优装载问题
题目描述
有n件物品和一个最大承重为w 的背包。第i件物品的重量是weight[i]每件只能用一次求装入背包的最多物品数量。
题目分析
因为我们只要求装入物品的数量所以装重的显然没有装轻的划算。因此将数组weight[i]按从小到大排序依次选择每个物品直到装不下为止就可以得到装入背包的最多物品数量。
代码
public static int stone(int n, int w, int[] weight) {Arrays.sort(weight); //将weight数组从小到大排序int max 0;int num 0;for(int i 0; i n; i) {if(max weight[i] w){max weight[i];num 1;}}return num;
}01背包问题
与上面的贪心背包问题而言贪心背包问题中物品的价值就是它的重量。 先前题主做的拿金币问题也可以说是一道背包问题不过其中背包的容量是无限的物品就是金币。
题目描述
有n件物品和一个最大承重为bagweight 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 卡码网第46题
题目分析
显然也是一道动态规划题也就是说背包问题是动态规划问题的子集当然这不重要。 我们先观察一下背包的属性
当前装入物品的个数当前装入物品的总重量容量当前装入物品的总价值关键在当前重量的基础上使得价值最高
注下文基本转述于代码随想录的网站只加了部分自己的理解
可转到代码随想录的网站去更深刻地理解01背包知识 代码随想录的链接戳这里进入
老规矩动归五部曲
定义dp数组
定义一个二维数组dp[i][j]将i定义为当前放入了多少个物品表示
从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。dp数组的值
确定dp数组递归公式
在决定是否放入第i个物品时显然有两种情况
要么不满足放入第i个物品的情况当物品i的重量大于背包j的重量时物品i无法放进背包中
dp[i][j] dp[i-1][j];要么满足放入第i个物品的情况此时比较放入前后的价值总和判断是否要放入。
dp[i][j] Math.max(dp[i-1][j], dp[i-1][j - weight[i] value[i];dp数组的初始化
从dp[i][j]出发
当背包容量j为0的时候则放不下任何物品背包中价值总和为0
for (int i 0 ; i weight.length; i) { dp[1][0] 0;再看其他情况。
因为递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 当中含有i-1即我们在遍历时肯定从i1的时候开始遍历那么物品为0的时候就一定要初始化。 此时考虑是否可以加入物品0 当 j weight[0]的时候dp[0][j] 为 0当j weight[0]时dp[0][j] 为value[0]
for (int j 0 ; j weight[0]; j) // 如果把dp数组预先初始化为0了这一步可以省略dp[0][j] 0;for (int j weight[0]; j bagweight; j) dp[0][j] value[0];其他位置可以任意初始化但是一开始就统一把dp数组统一初始为0更方便一些。
dp数组的遍历顺序
显然有两个遍历的维度物品与背包容量 先遍历物品或先遍历背包容量呢。 这里两种遍历顺序都可以是因为递推的方向分别是由上得到与由左得到而两个遍历顺序都是会先得到递推公式需要的旧数据因此不影响。
//先遍历物品
for(int i 1; i weight.size(); i) { // 遍历物品for(int j 0; j bagweight; j) { // 遍历背包容量if (j weight[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}
}
//先遍历背包容量
for(int j 0; j bagweight; j) { // 遍历背包容量for(int i 1; i weight.size(); i) { // 遍历物品if (j weight[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}
}举例说明dp数组
代码
import java.util.Arrays;public class BagProblem {public static void main(String[] args) {int[] weight {1,3,4};//这里是代码随想录的示范用例int[] value {15,20,30};int bagSize 4;testWeightBagProblem(weight,value,bagSize);}public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 创建dp数组int goods weight.length; // 获取物品的数量int[][] dp new int[goods 1][bagSize 1]; // 给物品增加冗余维i 0 表示没有物品可选// 初始化dp数组默认全为0即可// 填充dp数组for (int i 1; i goods; i) {for (int j 1; j bagSize; j) {if (j weight[i - 1]) { // i - 1 对应物品 i/*** 当前背包的容量都没有当前物品i大的时候是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值*/dp[i][j] dp[i - 1][j];} else {/*** 当前背包的容量可以放下物品i* 那么此时分两种情况* 1、不放物品i* 2、放物品i* 比较这两种情况下哪种背包中物品的最大价值最大*/dp[i][j] Math.max(dp[i - 1][j] , dp[i - 1][j - weight[i - 1]] value[i - 1]); // i - 1 对应物品 i}}}// 打印dp数组for(int[] arr : dp){System.out.println(Arrays.toString(arr));}}
}
