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

贪心算法是一种简单而有效的算法，通常应用于优化问题，例如最小化时间、最大化利润等。其基本思想是，在每一步选择中都采取当前状态下最优的选择，以期望最终结果是全局最优的。

以下是 Java 实现贪心算法的代码示例，解决的是经典的背包问题：

import java.util.Arrays;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        int[] weights = {2, 5, 4, 7, 1, 3, 8};
        int[] values = {10, 20, 15, 25, 5, 10, 15};
        int capacity = 10;

        double maxValue = knapsack(weights, values, capacity);
        System.out.println('Max value: ' + maxValue);
    }

    public static double knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        double[] ratios = new double[n];
        for (int i = 0; i < n; i++) {
            ratios[i] = (double) values[i] / weights[i];
        }

        double maxValue = 0;
        while (capacity > 0) {
            int bestItem = findBestItem(ratios);
            if (bestItem == -1) {
                break;
            }

            int weight = Math.min(capacity, weights[bestItem]);
            maxValue += weight * ratios[bestItem];
            capacity -= weight;
            ratios[bestItem] = 0;
        }

        return maxValue;
    }

    public static int findBestItem(double[] ratios) {
        int bestItem = -1;
        double bestRatio = 0;
        for (int i = 0; i < ratios.length; i++) {
            if (ratios[i] > bestRatio) {
                bestRatio = ratios[i];
                bestItem = i;
            }
        }
        return bestItem;
    }
}

代码中，knapsack 方法实现了贪心算法的核心逻辑，使用循环不断选择当前最优的物品放入背包，直到背包装满或物品全部选完。findBestItem 方法用于找到当前剩余物品中价值重量比最高的物品，即当前最优的选择。这里使用 ratios 数组记录每个物品的价值重量比，然后从中找到最大值。

这个代码示例的实现非常简单直接，没有使用复杂的数据结构或算法，适合初学者学习和实践。同时，这个算法也可以用于解决其他类似的优化问题，例如最小化成本、最大化收益等。