蓝桥杯算法提高VIP-快乐司机-题解（Java代码）贪心算法（小白，还请大佬多多指教）

解题思路:
            如题，一个物件有两个属性（pi质量，gi价值）这时就可以考虑使用咱们java的面向对象的思想了，先创建一个Node对象，为了后续排序和贪心算法的方便，添加一个di属性用来表示物件的价值比（pi/gi）.
注意事项:
        因为排序需要使用集合里面的sort(Comparator<? super E> c)方法，然后自定义排序方法：

public int compare(Node o1, Node o2) {
                    if (o1.di == o2.di) {
                        return 0;
                    }else {
                        return o1.di<o2.di?1:-1;
                    }
                }

参考代码:

mport java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class 快乐司机1917 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Node> list = new ArrayList<>();
        double sum=0;//总价值
        int page=0;//当前总质量
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();//可选物件个数
            int max = scanner.nextInt();//载货量
            for (int i = 0; i < n; i++) {
                Node node = new Node(scanner.nextInt(), scanner.nextInt());
                list.add(node);//加入集合
            }
            list.sort(new Comparator<Node>() {//重写comparator函数,使其按照自定义的模式去排序
                @Override
                public int compare(Node o1, Node o2) {
                    if (o1.di == o2.di) {
                        return 0;
                    }else {
                        return o1.di<o2.di?1:-1;
                    }
                }
            });
            for (int i = 0; i <list.size() ; i++) {
                Node node = list.get(i);
                if (page + node.gi <= max) {//当容量能容纳此物件时
                    page+=node.gi;//当前容量增加
                    sum+=node.pi;//当总价值
                }else {
                    sum+=(max-page)*node.di;//当当前容量无法容纳时  如 当前题的最大容量是36 但是 物件的容量超过时
                    break;
                }
            }
            System.out.printf("%.1f",sum);//进行格式输出
        }

    }
}

class Node{
    int gi;//物品的质量
    int pi;//物品的价值
    double di;//物品的价值比

    public Node(int gi,int pi) {
        this.gi = gi;
        this.pi=pi;
        this.di=1.0*pi/gi;
    }
}