编辑代码

package greedy;

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

class Fruit {
    public String name;//水果的名字
    public double totalWeight;//当前水果拥有的总重量
    public double totalValue;//当前水果的总价值

    Fruit(String name, double weight, double value) {    //所有属性值作为参数的构造方法
        this.name = name;
        this.totalWeight = weight;
        this.totalValue = value;
    }

    Fruit(Fruit item) {   //对象作为参数的构造方法
        this.name = item.name;
        this.totalWeight = item.totalWeight;
        this.totalValue = item.totalValue;
    }
}

public class GreedyFruitBackpack {
    //输入：背包的容量，供挑选的水果信息
    //输出：存储被装进背包的水果的列表
    public static LinkedList<Fruit> packFruit(int packCapacity, Fruit[] items){
        LinkedList<Fruit> fruits = new LinkedList<Fruit>(); // 定义列表记录需要装进背包的水果

        //1. 按照单价从高到低进行排序
        Arrays.sort(items, new Comparator<Fruit>() { 
            public int compare(Fruit left, Fruit right) { //重写Comparator接口的compare方法，按照我们所需的要求排序，即按照单价降序排
                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;
                }
            }
        });
        // System.out.println(items.toString());
        //2. 单价从高到低依次取出水果
        int leftPackCapacity = packCapacity;    
        for (int i = 0; i < items.length; ++i) {
            if (leftPackCapacity > items[i].totalWeight) {  
                //如果当前放得下贡献值最高的水果的所有重量，则全放进去。
                leftPackCapacity -= items[i].totalWeight;
                fruits.add(new Fruit(items[i]));
            } else {
                //如果当前背包剩余的重量不足以装入当前水果的全部重量，则需要装入当前水果的重量为背包剩余重量。
                double unitPrice = items[i].totalValue/items[i].totalWeight;
                double packWeight = leftPackCapacity;
                double packValue = packWeight * unitPrice;  //最后一种水果的价值
                fruits.add(new Fruit(items[i].name, packWeight, packValue));
                leftPackCapacity = 0;
                break;  //因为背包没有剩余重量了，剩余的水果不用再看了，可以退出循环了。
            }
        }

        return fruits;
    }
    public static void test() {
        Fruit[] items = {
            new Fruit("苹果", 15, 300),
            new Fruit("香蕉", 18, 180),
            new Fruit("橘子", 10, 150),
            new Fruit("猕猴桃", 9, 270),
        };
 
        LinkedList<Fruit> fruits = packFruit(20, items);

        double maxValue = 0;

        System.out.println("装了如下水果：");
        for (int i = 0; i < fruits.size(); ++i) {
            maxValue += fruits.get(i).totalValue;
            System.out.println(fruits.get(i).name + " 重量：" + fruits.get(i).totalWeight + "kg");
        }

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