贪心算法的应用(贪心算法是一种什么算法)

题目来自洛谷，原题链接：https://www.luogu.com.cn/problem/P2240

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100) 堆金币，第 i 堆金币的总重量

和总价值分别是 mi,vi(1≤mi,vi≤100)。阿里巴巴有一个承重量为 (T≤1000) 的背包，但并不一

定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分

割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价

值的金币？

输入格式

第一行两个整数 N,TN,T。

接下来 N 行，每行两个整数 mi,vi 。

输出格式

一个实数表示答案，输出两位小数

输入输出样例

输入

4 50
10 60
20 100
30 120
15 45

输出

240.00

题目分析

先按照价值比对金币堆排序，优先放入价值比大的金币堆。

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


public class Main {
    static class Coin {
        int m;
        int v;
        double v_m;

        Coin(int m, int v) {
            this.m = m;
            this.v = v;
            this.v_m = (double) v / (double) m;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList coins = new ArrayList<>();
        int n = scanner.nextInt();
        int t = scanner.nextInt();
        double w = 0;
        for (int i = 0; i < n; i++) {
            int m = scanner.nextInt();
            int v = scanner.nextInt();
            coins.add(new Coin(m, v));
        }
        Collections.sort(coins, new Comparator() {
            @Override
            public int compare(Coin o1, Coin o2) {
                if (o1.v_m == o2.v_m) return 0;
                else return o1.v_m > o2.v_m ? -1 : 1;
            }
        });
        for (int i = 0; i < n; i++) {
            if (t > coins.get(i).m) {
                w += coins.get(i).v;
                t -= coins.get(i).m;
            } else if (0 < t && t < coins.get(i).m) {
                w += t * coins.get(i).v_m;
                t = 0;
            } else break;
        }
        System.out.printf("%.2f", w);
    }
}

题目来自洛谷，原题链接：https://www.luogu.com.cn/problem/P1223

题目描述

有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 Ti，请编程找出这 n 个人排

队的一种顺序，使得 n 个人的平均等待时间最小。

输入格式

第一行为一个整数 n。

第二行 n 个整数，第 i个整数 Ti，表示第 i 个人的等待时间 Ti 。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均

等待时间（输出结果精确到小数点后两位）。

输入输出样例

输入

10 
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
291.90

代码

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


public class Main {
    static class Water {
        int water;
        int id;
        Water(int water, int id) {
            this.water = water;
            this.id = id;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList waters = new ArrayList<>();
        int n = scanner.nextInt();
        double time = 0L;
        for (int i = 1; i <= n; i++) {
            int water = scanner.nextInt();
            waters.add(new Water(water, i));
        }
        Collections.sort(waters, new Comparator() {
            @Override
            public int compare(Water o1, Water o2) {
                return o1.water - o2.water;
            }
        });
        int len = waters.size();
        for (int i = 0; i < len; i++) {
            System.out.printf("%d ", waters.get(i).id);
            time += waters.get(i).water * (len - i - 1);
        }
        System.out.println();
        System.out.printf("%.2f", time / n);
    }
}