用Java实现贪心算法

贪心算法是一种基于贪心策略的算法，它在每一步选择中都采取在当前状态下最好或最优的选择，从而希望能够导致结果是全局最好或最优的算法。

以下是一个用Java实现贪心算法求解背包问题的例子：

import java.util.Arrays;

public class GreedyAlgorithm {

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        double maxValue = getMaxValue(weights, values, capacity);
        System.out.println("The maximum value we can get is " + maxValue);
    }

    public static double getMaxValue(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i], i);
        }
        Arrays.sort(items);

        double maxValue = 0;
        for (Item item : items) {
            int curWeight = item.weight;
            int curValue = item.value;
            if (capacity - curWeight >= 0) {
                capacity -= curWeight;
                maxValue += curValue;
            } else {
                double fraction = ((double) capacity) / ((double) curWeight);
                maxValue += (curValue * fraction);
                break;
            }
        }
        return maxValue;
    }

    static class Item implements Comparable<Item> {
        int weight;
        int value;
        int index;

        public Item(int weight, int value, int index) {
            this.weight = weight;
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(Item item) {
            double ratio1 = (double) value / (double) weight;
            double ratio2 = (double) item.value / (double) item.weight;
            return Double.compare(ratio2, ratio1);
        }
    }
}

在这个例子中，我们定义了一个Item类来表示每个物品的重量、价值和索引。然后我们将所有的物品按照价值重量比从大到小排序，然后依次取出每个物品，如果当前物品可以完全放入背包，则将其放入背包并更新背包容量和最大价值；否则，将其部分放入背包，并更新背包容量和最大价值。

这个例子仅仅是贪心算法的一个简单运用，实际上贪心算法的应用非常广泛，例如最小生成树、最短路径、图着色等等。