经典算法题12-贪心算法

一. 引入

在日常生活中，经常遇到找零钱的问题。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？

很显然，每一步尽可能用面值大的纸币即可。这就是日常生活中贪心算法思想的使用。

二. 概念

百度百科的定义是：

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心是一种特殊的动态规划，动态规划的本质是独立的子问题，而贪心则是每次可以找到最优的独立子问题。后面我会细说两者的异同点。

三.最小生成树

图示

生成树，就是用边来把所有的顶点连通起来，前提条件是最后形成的连通图中不能存在回路，所以就形成这样一个无向图。

推理：假设图中的顶点有n个，则生成树的边有n-1条，多一条会存在回路，少一路则不能把所有顶点连通起来，如果非要在图中加上权重，则生成树中权重最小的叫做最小生成树。

Prim算法

算法简单描述

 1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；
 2. 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
 3. 重复下列操作，直到Vnew = V：
     a.在集合E中选取权值最小的边<u,v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
     b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
 4. 输出：使用集合Vnew和Enew来描述所得到的最小生成树。

• 1

四.Prim编码

图的存储有很多方式，邻接矩阵，邻接表，十字链表等等，当然都有自己的适合场景，下面分别用邻接矩阵和邻接表。
其中邻接矩阵需要采用两个数组，一个是保存顶点信息的一维数组，另一个是保存边信息的二维数组。

邻接矩阵：

/*
 * prim最小生成树
 *
 * 参数说明：
 * start -- 从图中的第start个元素开始，生成最小树
 */
    public void prim(int start) {
        int num = mVexs.length;         // 顶点个数
        int index=0;                    // prim最小树的索引，即prims数组的索引
        char[] prims  = new char[num];  // prim最小树的结果数组
        int[] weights = new int[num];   // 顶点间边的权值
 
        // prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。
        prims[index++] = mVexs[start];
 
        // 初始化"顶点的权值数组"，
        // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
        for (int i = 0; i < num; i++ )
            weights[i] = mMatrix[start][i];
        // 将第start个顶点的权值初始化为0。
        // 可以理解为"第start个顶点到它自身的距离为0"。
        weights[start] = 0;
 
        for (int i = 0; i < num; i++) {
            // 由于从start开始的，因此不需要再对第start个顶点进行处理。
            if(start == i)
                continue;
 
            int j = 0;
            int k = 0;
            int min = INF;
            // 在未被加入到最小生成树的顶点中，找出权值最小的顶点。