贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。简单来说，这种算法在每一步都选择对当前问题最好的解决方案，而不考虑将来的后果。它不能保证最终得到的解是最佳的，但在某些问题上效果非常好。

这里是一个使用 Go 语言实现的简单贪心算法的例子。假设我们有一个找零问题，我们需要找给顾客尽可能少的硬币。假设有 1, 5, 10, 25 分的硬币，我们需要找零 n 分。

package main

import (
    "fmt"
    "sort"
)

func findMinCoins(coins []int, amount int) []int {
    sort.Sort(sort.Reverse(sort.IntSlice(coins)))
    result := make([]int, 0)

    for _, coin := range coins {
        for amount >= coin {
            amount -= coin
            result = append(result, coin)
        }
    }
    return result
}

func main() {
    coins := []int{1, 5, 10, 25}
    amount := 47 // 例子：需要找零 47 分
    minCoins := findMinCoins(coins, amount)
    fmt.Println("Coins to give:", minCoins)
}

在这个例子中，findMinCoins 函数接受一个硬币列表和一个需要找零的总金额，然后返回构成该金额的最小硬币数目。该函数首先将硬币按降序排序，然后遍历每种硬币，尽可能多地使用每种硬币，直到不能使用该硬币为止。这个过程重复进行，直到找齐所有的零钱。

会议问题

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间（给你一个数组，里面是一个个具体的项目），你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次

贪心策略：结束时间短的优先安排，安排后把不能安排的会议去掉，再次重复这个过程

构建会议的数据结构：

public static class Program {
  public int start;
  public int end;

  public Program(int start, int end) {
    this.start = start;
    this.end = end;
  }
}

具体的贪心算法：

/**
 * 定义一个比较器
 */
public static class ProgramComparator implements Comparator<Program> {

  @Override
  public int compare(Program o1, Program o2) {
    return o1.end - o2.end;
  }

  /**
   * 最优的次数
   *
   * @param programs 需要安排会议
   * @param timePoint 从什么时间点开始安排
   * @return 最优的排序可以安排几个会议
   */
  public static int bestArrange(Program[] programs, int timePoint) {
    Arrays.sort(programs, new ProgramComparator());
    int result = 0;
    for (int i = 0; i < programs.length; i++) {
      if (timePoint <= programs[i].start) {
        result++;
        timePoint = programs[i].end;
      }
    }
    return result;
  }
  
}

所以这个贪心策略怎么来的？接着往下看：

贪心算法解题套路

1、实现一个不依靠贪心策略的解法 X，可以用最暴力的尝试（例如暴力枚举） 2、脑补出策略 A、贪心策略 B、贪心策略 C... 3、用解法 X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确 4、不要纠结贪心策略的证明

切割金条问题

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为 20 的金条，不管切成长度多大的两半，都要花费 20 个铜板。一群人想整分整块金条，怎么分最省铜板？

例如，给定数组 {10, 20, 30}，代表一共三个人，整块金条长度为 10 + 20 + 30 = 60。金条要分成 10,20,30 三个部分。如果先把长度 60 的金条分成 10 和 50，花费 60；再把长度 50 的金条分成 20 和 30，花费 50；一共花费 110 铜板。但是如果先把长度 60 的金条分成 30 和 30，花费 60；再把长度 30 金条分成 10 和 20，花费 30；一共花费 90 铜板。输入一个数组，返回分割的最小代价。

贪心算法就是赫夫曼编码树，证明略

给定 n 个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树（Huffman Tree）

可以看到这个最优策略画成图就是赫夫曼树，即最小加权路径

下面使用小根堆构建赫夫曼树

public static int lessMoney(int[] arr) {
  PriorityQueue<Integer> pQ = new PriorityQueue<>();
  // 先把数都存进小根堆里面
  for (int i = 0; i < arr.length; i++) {
    pQ.add(arr[i]);
  }
  int sum = 0;
  int cur = 0;
  // 因为是小根堆，所以直接是从最小开始加的
  while (pQ.size() > 1) {
    // 这里其实模拟赫夫曼树从底到头的一次遍历（赫夫曼树最小的位于最后面）
    cur = pQ.poll() + pQ.poll();
    sum += cur;
    // 把数丢回小根堆
    pQ.add(cur);
  }
  // 最后把沿途所有代价返回出去
  return sum;
}

贪心算法​

会议问题​

贪心算法解题套路​

切割金条问题​

贪心算法

会议问题

贪心算法解题套路

切割金条问题