14天阅读挑战赛

1.概念

从贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优。所以自然而然，贪心算法得出的最后的解，不一定是问题的最优解，很有可能是近似解。

1.1 两个特性

算法的基本要素：

• 最优子结构性质：

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

• 贪心选择性质：

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

1.2 与暴力、动态规划的区别与联系

贪心算法最容易和暴力算法、动态规划相互混淆。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
动态规划算法，最基础的是要找到动态转移方程，然后使用递归或者栈的操作，去实现。
贪心算法，最基础的是最初要选择一种贪心策略（例如：每次选择最大的or最小的），然后一步一步的去达到目的。
暴力算法，是在找不到任何特征的前提下，遍历所有可能，去找寻答案的一种算法。

2.贪心的实际使用场景

2.1 冒泡排序

冒泡排序算法的实现思想是：
“每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。
动画演示：

java代码实现

import java.util.Arrays;

class Main {
    public static void main(String[] args) {
        int[] a = new int[] { 2, 22, 1, 0, 99, 2, 5, 19, 32 };
        bubbleSort(a);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 冒泡排序
     * 
     * @Title: bubbleSort
     * @Description:
     * @author: itbird
     * @date 2022年10月20日 上午10:39:28
     * @param a
     *            void 时间复杂度: O(N^2) 空间复杂度: O(1)
     */
    private static void bubbleSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }

        boolean swap = false;
        for (int i = 0; i < a.length; i++) {
            swap = false;
            // 通过每次遍历，将最大元素移动到数组末尾
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swap = true;
                }
            }

            // 剪枝，如果某一轮对比中，没有进行交换，说明当前数组已经有序
            if (!swap) {
                break;
            }
        }
    }

}

2.2 最优装载问题

问题描述：有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
解题思路：大家发现这时的问题相比于背包问题，有两点不同，一没有货物价值的考虑，二货物也不可分割，只需考虑装载的物品需要最多。那么此处其实我们采取贪心策略即可，即每次选择最小的重量的集装箱，直到达到轮船的最大承载力 。

• 申明k，k代表当前轮船的剩余装载力还要多少，初始值为C
• 先将w数组排序
• 遍历w数组，然后从中取出货物，逐渐往船上装载，直到装载不上

Java代码实现：

class Main {
    public static void main(String[] args) {
        int c = 200; // 最大承载力为200
        int[] w = new int[] { 2, 22, 1, 0, 99, 2, 5, 19, 32 }; // 每个集装箱的重量大小

        // 先将w数组排序
        bubbleSort(w);

        int k = c; // k代表当前轮船的剩余装载力还要多少
        // 遍历w数组，然后从中取出货物，逐渐往船上装载，直到装载不上
        for (int i = 0; i < w.length; i++) {
            if (k > w[i]) {
                // 如果当前轮船还可以装载，则装载此集装箱w[i]
                k -= w[i];
            } else {
                break;
            }
        }

        System.out.println("轮船的最优装载量为:" + (c - k));
    }

    /**
     * 冒泡排序
     * 
     * @Title: bubbleSort
     * @Description:
     * @author: itbird
     * @date 2022年10月20日 上午10:39:28
     * @param a
     *            void 时间复杂度: O(N^2) 空间复杂度: O(1)
     */
    private static void bubbleSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }

        boolean swap = false;
        for (int i = 0; i < a.length; i++) {
            swap = false;
            // 通过每次遍历，将最大元素移动到数组末尾
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swap = true;
                }
            }

            // 剪枝，如果某一轮对比中，没有进行交换，说明当前数组已经有序
            if (!swap) {
                break;
            }
        }
    }

}

2.3 背包问题（货物可拆解）

问题描述：我们有一辆三轮车，某天发现了一个山洞，假设山洞中有n中宝物，每种宝物有一定的重量和相应的价值，而三轮车的运载能力有限，只能运走m重量的宝物，一种宝物只可以拿一样，宝物可以分割，那么怎么才可以一次拿走最大价值的宝物呢？。
解题思路：分析问题中，大家发现相比于0-1背包问题来说，此问题中的宝物可以分割。那么我们采取贪心策略，选择怎样的贪心策略呢？

• 每次选择最轻的宝物？
• 每次选择价值最大的宝物？
• 每次选择单位价值最大的宝物？

思考一下，如果选价值最大的宝物，但重量非常大，也是不行的，因为运载能力是有限的，所以第 1 种策略舍弃；如果选重量最小的物品装入，那么其价值不一定高，所以不能在总重限制的情况下保证价值最大，第 2 种策略舍弃；而第 3 种是每次选取单位重量价值最大的宝物，也就是说每次选择性价比（价值/重量）最高的宝物，如果可以达到运载重量 m，那么一定能得到价值最大。
因此采用第 3 种贪心策略，每次从剩下的宝物中选择性价比最高的宝物。

Java代码实现：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Main {
    public static void main(String[] args) {
        int m = 19; // 最大承载力为19
        double[] w = new double[] { 2, 6, 7, 4, 10, 3 }; // 每个宝物的重量大小
        double[] v = new double[] { 8, 1, 9, 3, 2, 4 }; // 每个宝物的价值大小

        List<Treasure> treaseures = new ArrayList<Treasure>();
        // 遍历w、v将输入数据，封装为宝物信息
        for (int i = 0; i < v.length; i++) {
            treaseures.add(new Treasure(w[i], v[i]));
        }

        // 对宝物信息封装，以单位价值进行排序
        Collections.sort(treaseures);

        int k = m; // k代表当前三轮车的剩余承载力
        double maxV = 0; // 最大价值
        for (int i = 0; i < treaseures.size(); i++) {
            if (k > treaseures.get(i).w) {
                k -= treaseures.get(i).w;
                maxV += treaseures.get(i).v;
            } else {
                maxV += k * treaseures.get(i).v / treaseures.get(i).w;
            }
        }
        System.out.println("所能一次装载的最大价值宝物为：" + maxV);
    }

    /**
     * 宝物的类
     * 
     * @author itbird
     *
     */
    static class Treasure implements Comparable<Treasure> {
        // 宝物重量
        double w;
        // 宝物价值
        double v;

        public Treasure(double w, double v) {
            this.w = w;
            this.v = v;
        }

        @Override
        public int compareTo(Treasure o) {
            return (int) (v / w - o.v / o.w);
        }
    }
}