建站主机,自己公司网站如何添加qq,python网站开发教程,网站怎么做付费项目背包问题分类见下图 参考学习点击#xff1a;代码随想录01背包讲解
01背包问题#xff1a; 核心思路#xff1a; 1、先遍历物品个数#xff0c;再遍历背包容量。因为容量最先是最大的#xff0c;往背包里放物品#xff0c;所以背包容量在慢慢减少#xff0c;但背包容量…背包问题分类见下图 参考学习点击代码随想录01背包讲解
01背包问题 核心思路 1、先遍历物品个数再遍历背包容量。因为容量最先是最大的往背包里放物品所以背包容量在慢慢减少但背包容量需要大于每一个物品体积 2、每个物品有2个选择选中和不选中。 3、选中的结果是背包剩余容量的最大价值选中物品的价值 4、不选中的结果是背包剩余容量还是不变最大价值还是背包剩余容量的最大价值 public static void main(String[] args) {int[] weight {1, 3, 4}; //每个物品体积int[] value {15, 20, 30}; // 每个物品价值int bagWight 4; // 背包容量testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){//定义dp数组dp[j]表示背包容量为j时能获得的最大价值int[] dp new int[bagWeight 1];//背包容量来定义dp数组for (int i 0; i weight.length; i){ //先遍历物品for (int j bagWeight; j weight[i]; j--){ //再遍历背包背包容量是从最大一直慢慢减少 //每个物品有2种选择选中与不选中选中的话背包价值背包容量剩余物品的价值在加上选中物品的价值//不选中的话背包价值背包容量j的价值dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}//打印dp数组for (int j 0; j bagWeight; j){System.out.print(dp[j] );}} 完全背包问题
