想在意大利做购物网站,好的网站建设,那些是flash做的网站,广州微信网站建设公司哪家好#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 博客目录 1.问题描述2.问题解析3.二维解答4.一维解答5.继续优化 1.问题描述 0-1 背包问题0-1 Knapsack Problem是一个经典的组合优化问题通常出现在计算机科学和数学中。它的背景是在给定一组物品每个物品有一个特定的重量和价值以及一个固定容量的背包。问题的目标是确定应该选择哪些物品放入背包以使得它们的总重量不超过背包的容量并且它们的总价值最大化。 0-1 背包问题之所以称为 0-1是因为对于每个物品你只有两种选择要么将它放入背包表示为 1要么不放入背包表示为 0。不能将一个物品部分放入背包。 2.问题解析
/*1. n个物品都是固体有重量和价值2. 现在你要取走不超过 10克 的物品3. 每次可以不拿或全拿问最高价值是多少编号 重量(g) 价值(元) 简称1 4 1600 黄金一块 400 A2 8 2400 红宝石一粒 300 R3 5 30 白银一块 S4 1 1_000_000 钻石一粒 D1_001_630 贪心解1_002_400 正确解
*/
/*0 1 2 3 4 5 6 7 8 9 100 0 0 0 0 A A A A A A A 黄金1 0 0 0 0 A A A A R R R 红宝石2 0 0 0 0 A A A A R R R 白银3 0 D D D D DA DA DA DA DR DR 钻石if(装不下) {dp[i][j] dp[i-1][j]} else { 装得下dp[i][j] max(dp[i-1][j], item.value dp[i-1][j-item.weight])}
*/3.二维解答
static class Item {int index;String name;int weight;int value;public Item(int index, String name, int weight, int value) {this.index index;this.name name;this.weight weight;this.value value;}Overridepublic String toString() {return Item( name );}
}public static void main(String[] args) {Item[] items new Item[]{new Item(1, 黄金, 4, 1600),new Item(2, 宝石, 8, 2400),new Item(3, 白银, 5, 30),new Item(4, 钻石, 1, 10_000),};System.out.println(select(items, 10));
}static int select(Item[] items, int total) {int[][] dp new int[items.length][total 1];print(dp);final Item item0 items[0];for (int j 0; j total 1; j) {if (j item0.weight) {//装得下dp[0][j] item0.value;}}print(dp);for (int i 1; i items.length; i) {final Item item items[i];for (int j 0; j total 1; j) {if (j item.weight) {//装得下dp[i][j] Integer.max(dp[i - 1][j], item.value dp[i - 1][j - item.weight]);} else {dp[i][j] dp[i - 1][j];}}print(dp);}return dp[items.length - 1][total];
}static void print(int[][] dp) {System.out.println(StringUtil.repeat( -, 20));Object[] array IntStream.range(0, dp[0].length 1).boxed().toArray();System.out.printf((StringUtil.repeat(%5d , dp[0].length)) %n, array);for (int[] d : dp) {array Arrays.stream(d).boxed().toArray();System.out.printf((StringUtil.repeat(%5d , d.length)) %n, array);}
}4.一维解答
static class Item {int index;String name;int weight;int value;public Item(int index, String name, int weight, int value) {this.index index;this.name name;this.weight weight;this.value value;}Overridepublic String toString() {return Item( name );}
}public static void main(String[] args) {Item[] items new Item[]{new Item(1, 黄金, 4, 1600),new Item(2, 宝石, 8, 2400),new Item(3, 白银, 5, 30),new Item(4, 钻石, 1, 10_000),};System.out.println(select(items, 10));
}static int select(Item[] items, int total) {int[] dp new int[total 1];System.out.println(Arrays.toString(dp));final Item item0 items[0];for (int j 0; j total 1; j) {if (j item0.weight) {//装得下dp[j] item0.value;}}System.out.println(Arrays.toString(dp));for (int i 1; i items.length; i) {final Item item items[i];for (int j total; j 0; j--) {if (j item.weight) {//装得下dp[j] Integer.max(dp[j], item.value dp[j - item.weight]);}}System.out.println(Arrays.toString(dp));}return dp[total];
}5.继续优化
static class Item {int index;String name;int weight;int value;public Item(int index, String name, int weight, int value) {this.index index;this.name name;this.weight weight;this.value value;}Overridepublic String toString() {return Item( name );}
}public static void main(String[] args) {Item[] items new Item[]{new Item(1, 黄金, 4, 1600),new Item(2, 宝石, 8, 2400),new Item(3, 白银, 5, 30),new Item(4, 钻石, 1, 10_000),};System.out.println(select(items, 10));
}static int select(Item[] items, int total) {int[] dp new int[total 1];for (int i 0; i items.length; i) {final Item item items[i];for (int j total; j 0; j--) {if (j item.weight) {//装得下dp[j] Integer.max(dp[j], item.value dp[j - item.weight]);}}System.out.println(Arrays.toString(dp));}return dp[total];
}注意内层循环需要倒序否则 dp[j - item.weight] 的结果会被提前覆盖 觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
