Java 贪心算法实现：背包问题示例

{"title":"Java 贪心算法实现：背包问题示例", "description":"本文将使用 Java 代码演示如何实现贪心算法，并以背包问题为例进行说明。贪心算法选择单位重量价值最高的物品来最大化总价值。", "keywords":"贪心算法, 背包问题, Java, 算法实现, 编程示例", "content":""好的，下面是一个使用Java实现贪心算法的示例：\n\njava\nimport java.util.ArrayList;\nimport java.util.Collections;\nimport java.util.Comparator;\nimport java.util.List;\n\\npublic class GreedyAlgorithm {\n public static void main(String[] args) {\n List<Item> items = new ArrayList<>();\n items.add(new Item("item1", 4, 12));\n items.add(new Item("item2", 2, 10));\n items.add(new Item("item3", 6, 18));\n items.add(new Item("item4", 1, 6));\n int capacity = 10;\n\\n List<Item> selectedItems = greedyAlgorithm(items, capacity);\n System.out.println("Selected items:");\n for (Item item : selectedItems) {\n System.out.println(item.getName());\n }\n }\n\\n public static List<Item> greedyAlgorithm(List<Item> items, int capacity) {\n List<Item> selectedItems = new ArrayList<>();\n Collections.sort(items, Comparator.comparingDouble(Item::getValuePerWeight).reversed());\n\\n for (Item item : items) {\n if (capacity >= item.getWeight()) {\n selectedItems.add(item);\n capacity -= item.getWeight();\n }\n }\n\\n return selectedItems;\n }\n\\n static class Item {\n private String name;\n private int weight;\n private int value;\n\\n public Item(String name, int weight, int value) {\n this.name = name;\n this.weight = weight;\n this.value = value;\n }\n\\n public String getName() {\n return name;\n }\n\\n public int getWeight() {\n return weight;\n }\n\\n public int getValue() {\n return value;\n }\n\\n public double getValuePerWeight() {\n return (double) value / weight;\n }\n }\n}\n\n\n这个示例实现了一个贪心算法来解决一个背包问题。背包有一定的容量，每个物品有自己的重量和价值，目标是选择一些物品放入背包中以使得总价值最大化。贪心算法的策略是选择单位重量价值最高的物品放入背包中。在示例中，我们使用Item类来表示物品，然后使用贪心算法来选择物品并计算总价值。最后，输出所选择的物品的名称。"}