用java 写一个贪心算法

下面是一个简单的 Java 实现贪心算法的示例：

假设有n个物品，每个物品有自己的价值和重量，现在有一个背包，它能承受的重量是m。我们将如何选择物品放入背包，使得背包中的总价值最大？

import java.util.Arrays;

public class GreedyAlgorithm {

    /**
     * 使用贪心算法解决0/1背包问题
     *
     * @param w 物品重量数组
     * @param v 物品价值数组
     * @param m 背包容量
     * @return 最大价值
     */
    public static int knapsack(int[] w, int[] v, int m) {
        int n = w.length;
        int[] index = new int[n];
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        // 按照单位重量的价值从大到小排序物品
        Arrays.sort(index, (a, b) -> Double.compare((double) v[b] / w[b], (double) v[a] / w[a]));
        int maxValue = 0;
        int currentWeight = 0;
        for (int i = 0; i < n; i++) {
            int itemIndex = index[i];
            if (currentWeight + w[itemIndex] <= m) {
                // 将物品放入背包中
                currentWeight += w[itemIndex];
                maxValue += v[itemIndex];
            } else {
                // 物品只能放一部分
                int remaining = m - currentWeight;
                maxValue += remaining * v[itemIndex] / w[itemIndex];
                break;
            }
        }
        return maxValue;
    }

    public static void main(String[] args) {
        int[] w = {2, 3, 4, 5};
        int[] v = {3, 4, 5, 6};
        int m = 8;
        int maxValue = knapsack(w, v, m);
        System.out.println("最大价值：" + maxValue);
    }
}

代码中的 knapsack 方法实现了使用贪心算法解决0/1背包问题的逻辑。它首先按照单位重量的价值从大到小排序物品，然后依次将物品放入背包中，直到背包装满或者所有物品都放完为止。如果无法放入整个物品，则只能放入一部分，贪心选择价值最高的部分放入背包中。最后返回背包中的最大价值。在 main 方法中，我们定义了一组简单的数据进行测试。