java贪心背包问题代码

Java中贪心算法解决背包问题的代码如下所示：

import java.util.*;

class ItemValue {
    double cost;
    double wt, val, ind;

    public ItemValue(double wt, double val, double ind) {
        this.wt = wt;
        this.val = val;
        this.ind = ind;
        cost = val / wt;
    }
}

class Knapsack {
    static double maxValue(int[] wt, int[] val, int capacity) {
        ItemValue[] iVal = new ItemValue[wt.length];

        for (int i = 0; i < wt.length; i++) {
            iVal[i] = new ItemValue(wt[i], val[i], i);
        }

        Arrays.sort(iVal, new Comparator<ItemValue>() {
            @Override
            public int compare(ItemValue o1, ItemValue o2) {
                return Double.compare(o2.cost, o1.cost);
            }
        });

        double totalValue = 0d;

        for (ItemValue i : iVal) {
            double curWt = (double) i.wt;
            double curVal = (double) i.val;

            if (capacity - curWt >= 0) {
                capacity -= curWt;
                totalValue += curVal;
            } else {
                double fraction = capacity / curWt;
                totalValue += (curVal * fraction);
                capacity -= (curWt * fraction);
                break;
            }
        }

        return totalValue;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] wt = { 10, 40, 20, 30 };
        int[] val = { 60, 40, 100, 120 };
        int capacity = 50;

        double maxValue = Knapsack.maxValue(wt, val, capacity);

        System.out.println("Maximum value we can obtain = " + maxValue);
    }
}

该代码实现了一个背包问题的贪心算法。其中，背包问题的定义是：给定n个物品和一个容量为W的背包。物品i的重量是wi，价值是vi。求装入背包的物品的最大价值。

代码使用了自定义的ItemValue类，存储每个物品的价值、重量、索引以及性价比。然后将所有物品按照性价比从大到小排序，然后依次加入背包中，直到背包装满或者物品已经全部加入为止。