编辑代码

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

class Main {
    public static void main(String[] args) {
        Knapsack knapsack=new Knapsack();
        Fruit[] fruits = {
                new Fruit("苹果", 15, 300),
                new Fruit("香蕉", 18, 180),
                new Fruit("橘子", 10, 150),
                new Fruit("猕猴桃", 9, 270),
        };
        knapsack.print(fruits, 20);
    }
}
class Fruit {
    public String name;
    public int weight;
    public int value;

    Fruit(String name, int weight, int value) {
        this.name = name;
        this.weight = weight;
        this.value = value;
    }

    Fruit(Fruit fruit) {
        this.name = fruit.name;
        this.weight = fruit.weight;
        this.value = fruit.value;
    }
}

class Knapsack
{
    public static LinkedList<Fruit> pick(int maxWeight, Fruit[] fruits){
        LinkedList<Fruit> pf = new LinkedList<Fruit>();
        // 按单价从高到低排序
        Arrays.sort(fruits, new Comparator<Fruit>() {
            @Override
            public int compare(Fruit f01, Fruit f02) {
                int fv01 = f01.value/ f01.weight;
                int fv02 = f02.value/f02.weight;
                if(fv01 > fv02)
                {
                    return -1;
                }
                else if(fv01 == fv02)
                {
                    return 0;
                }
                return 1;
            }
        });
        // 取水果，比较
        int capacity = maxWeight;
        for (int i = 0; i < fruits.length; i ++) {
            if(capacity > fruits[i].weight){
                capacity -= fruits[i].weight;
                pf.add(new Fruit(fruits[i]));
            }
            else{
                int price = fruits[i].value/fruits[i].weight;
                int weight = capacity;
                int value = weight * price;
                pf.add(new Fruit(fruits[i].name, weight, value));
                capacity = 0;
                break;
            }
        }
        return pf;
    }

    public static void print(Fruit[] fruits,int weight) {
        int maxValue = 0;
        LinkedList<Fruit> pf = pick(weight, fruits);
        System.out.println("背包装水果总价值最高的策略是：");
        for (int i = 0; i < pf.size(); i ++) {
            maxValue = maxValue+ pf.get(i).value;
            System.out.println( pf.get(i).weight + "千克" + pf.get(i).name );
        }
        System.out.println("总价值最高为：" + maxValue + "元");
    }
}