java:贪心法实现01背包问题

以下是Java中使用贪心算法实现01背包问题的代码：

import java.util.Arrays;

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {4, 6, 3, 4, 2}; // 物品重量
        int[] v = {10, 15, 6, 8, 4}; // 物品价值
        int capacity = 12; // 背包容量
        double maxValue = knapsack(w, v, capacity);
        System.out.println("最大价值为：" + maxValue);
    }

    public static double knapsack(int[] w, int[] v, int capacity) {
        int n = w.length;
        double[] valuePerWeight = new double[n]; // 每个物品的单位价值
        for (int i = 0; i < n; i++) {
            valuePerWeight[i] = (double) v[i] / w[i];
        }
        // 按照单位价值从大到小排序
        Integer[] index = new Integer[n];
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        Arrays.sort(index, (o1, o2) -> -Double.compare(valuePerWeight[o1], valuePerWeight[o2]));
        // 贪心选择物品
        double maxValue = 0;
        for (int i = 0; i < n; i++) {
            int j = index[i];
            if (w[j] <= capacity) {
                maxValue += v[j];
                capacity -= w[j];
            } else {
                maxValue += valuePerWeight[j] * capacity;
                break;
            }
        }
        return maxValue;
    }
}