Version: Next

贪心算法

  • 每一步都采取昂前状态下最优的选择（局部最优解），从而希望推导出全局最优解
  • 贪心法的应用：
    • 哈夫曼树
    • 最小生成树：Prim、Kruskal
    • 最短路径算法：Dijkstra

最优装载问题——海盗问题

  • 宝藏不能打碎，一旦打碎就失去价值
  • 海盗船载重量为W，每件宝藏的重量为w_i
  • 问如何尽可能多的搜刮走宝藏

贪心的体现：

  • 显然，每次都拿重量最小的宝藏即可，这种选择，突出一个每次都拿最轻，使船只载重量尽可能减少的小，即局部最优

例如：W = 30，w_i分别为：3 5 4 10 7 14 2 11

  • 选择2，剩下28
  • 选择3，剩下25
  • 选择4，剩下21
  • 选择5，剩下16
  • 选择7，剩下9

可装5个宝藏

/**
* 海盗船最优装载问题
*/
public class Pirate {
public static void main(String[] args) {
int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};
int W = 30;
int number = 0;
// 从小到大排序
Arrays.sort(weights);
for (int w_i : weights) {
if (W > w_i) { // 船载重比当前最轻宝藏还大，就拿走
W -= w_i;
number++;
}
}
System.out.println("number = " + number); // expect 5
}
}

零钱兑换问题

假设有25块、10块、5块、1块的纸币，现在要给客户41块钱的零钱，如何使用到的纸币张数最少？

  • 显然，优先拿大的就行，体现局部最优
/**
* 零钱兑换
*/
public class CoinChange {
private static void solve(int money) {
Integer[] faces = {1, 5, 10, 25};
int coinNum = 0;
// 从大到小排序
Arrays.sort(faces, (n1, n2) -> n2 - n1);
System.out.println("要给出 [" + money + "] 块钱");
for (Integer face : faces) {
while (money >= face) {
money -= face;
coinNum++;
System.out.println("给出一张 [" + face + "] 块钱的纸币，还需要找 [" + money + "] 块钱");
}
}
System.out.println("coinNum = " + coinNum);
}
public static void main(String[] args) {
solve(41);
System.out.println("---------------------------------------------");
solve(51);
}
}
运行结果
要给出 [41] 块钱
给出一张 [25] 块钱的纸币，还需要找 [16] 块钱
给出一张 [10] 块钱的纸币，还需要找 [6] 块钱
给出一张 [5] 块钱的纸币，还需要找 [1] 块钱
给出一张 [1] 块钱的纸币，还需要找 [0] 块钱
coinNum = 4
---------------------------------------------
要给出 [51] 块钱
给出一张 [25] 块钱的纸币，还需要找 [26] 块钱
给出一张 [25] 块钱的纸币，还需要找 [1] 块钱
给出一张 [1] 块钱的纸币，还需要找 [0] 块钱
coinNum = 3

更换面值发生的问题

将面值从25 10 5 1更换为25 20 5 1，再次执行给出41块钱

运行结果
要给出 [41] 块钱
给出一张 [25] 块钱的纸币，还需要找 [16] 块钱
给出一张 [5] 块钱的纸币，还需要找 [11] 块钱
给出一张 [5] 块钱的纸币，还需要找 [6] 块钱
给出一张 [5] 块钱的纸币，还需要找 [1] 块钱
给出一张 [1] 块钱的纸币，还需要找 [0] 块钱
coinNum = 5
问题：

此时出现了问题，上述运行结果并不是实际上的最优解，实际最优解应当是

  1. 给出一张20，剩下21
  2. 给出一张20，剩下1
  3. 给出一张1，结束

局部最优解 != 全局最优解

上述的例子说明，贪心策略强调的局部最优解并不一定能够得到全局最优解

  • 因为一般没有测试所有可能的解，就过早做出了决定，故无法达到全局最优解

  • 数目寸光，看不到长远效应，只选择当前眼下的最优解，一般作为其他算法的辅助算法

  • 综上，想要更好的解决这一问题，应当采用动态规划