贪心问题JAVA_java背包问题(贪心法)

好的，背包问题是一个经典的动态规划问题，但也可以使用贪心算法来解决。下面是使用贪心算法解决背包问题的JAVA代码：

import java.util.Arrays;

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weight = {10, 20, 30}; // 物品重量
        int[] value = {60, 100, 120}; // 物品价值
        int capacity = 50; // 背包容量
        double maxValue = getMaxValue(weight, value, capacity);
        System.out.println("背包能装的最大价值为：" + maxValue);
    }

    /**
     * 获取背包能装的最大价值
     * @param weight 物品重量
     * @param value 物品价值
     * @param capacity 背包容量
     * @return 背包能装的最大价值
     */
    public static double getMaxValue(int[] weight, int[] value, int capacity) {
        int n = weight.length;
        double[] unitValue = new double[n]; // 单位价值
        for (int i = 0; i < n; i++) {
            unitValue[i] = (double) value[i] / weight[i];
        }
        int[] index = new int[n]; // 物品索引
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        Arrays.sort(index, (i, j) -> Double.compare(unitValue[j], unitValue[i])); // 按单位价值从大到小排序
        double maxValue = 0; // 背包能装的最大价值
        for (int i = 0; i < n && capacity > 0; i++) {
            int j = index[i];
            double w = Math.min(weight[j], capacity); // 能装下的重量
            maxValue += w * unitValue[j]; // 能装下的最大价值
            capacity -= w;
        }
        return maxValue;
    }
}

在这个代码中，我们计算每个物品的单位价值，并按照单位价值从大到小排序，然后依次选择单位价值最大的物品放入背包中，直到背包无法再装下物品为止。

这里使用了lambda表达式来简化排序过程，如果不理解可以使用传统的Comparator或Comparable来进行排序。