编辑代码

package Greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

public class Backpack {

    public static LinkedList<GreedyItem> packBean(int packCapacity, GreedyItem[] items){
        LinkedList<GreedyItem> beans = new LinkedList<GreedyItem>(); 

        //按照单价从高到低进行排序
        Arrays.sort(items, new Comparator<GreedyItem>() {
            public int compare(GreedyItem left, GreedyItem right) {
                double leftUnitPrice = left.totalValue/left.totalWeight;
                double rightUnitPrice = right.totalValue/right.totalWeight;
                if (leftUnitPrice > rightUnitPrice){
                    return -1;
                }
                else if (leftUnitPrice == rightUnitPrice) {
                    return 0;
                }
                else {
                    return 1;
                }
            }
        });

        //从高到低依次取出物品
        int leftPackCapacity = packCapacity;
        for (int i = 0; i < items.length; ++i) {
            if (leftPackCapacity > items[i].totalWeight) {
                leftPackCapacity -= items[i].totalWeight;
                beans.add(new GreedyItem(items[i]));
            }
            else {
                double unitPrice = items[i].totalValue/items[i].totalWeight;
                double packWeight = leftPackCapacity;
                double packValue = packWeight * unitPrice;
                beans.add(new GreedyItem(items[i].name, packWeight, packValue));
                leftPackCapacity = 0;
                break;
            }
        }

        return beans;
    }
    public static void test() {
        GreedyItem[] items = {
                new GreedyItem("苹果",    15, 300),
                new GreedyItem("香蕉",    18, 180),
                new GreedyItem("桔子",    10, 150),
                new GreedyItem("猕猴桃",   9,  270)
        };

        LinkedList<GreedyItem> beans = packBean(20, items);

        double maxValue = 0;

        System.out.println("装了如下物品：");
        for (GreedyItem bean : beans) {
            maxValue += bean.totalValue;
            System.out.println(bean.name + " " + bean.totalWeight);
        }

        System.out.println("总价值：" + maxValue);

    }

    public static void main(String[] args) {
        Backpack.test();
    }

}

class Item {
    public String name;
    public int value;
    public int weight;

    public Item(String n, int v, int w) {
        this.name = n;
        this.value = v;
        this.weight = w;
    }
}

class GreedyItem {
    public String name;
    public double totalWeight;
    public double totalValue;

    public GreedyItem(String itemName, double weight, double value) {
        this.name = itemName;
        this.totalWeight = weight;
        this.totalValue = value;
    }

    public GreedyItem(GreedyItem item) {
        this.name = item.name;
        this.totalWeight = item.totalWeight;
        this.totalValue = item.totalValue;
    }
}