贪心算法

我对贪心算法的理解就是：

当一个问题比较大时，不能从全局上得到问题的最优解，这个时候就把这个大问题划分成小问题，对于每个小问题都进行求出最优解，最后把这些小问题的最优解整合在一起就是整体的最优解（其实有可能不是最优解，因为有时候并不能证明哪个时最优解，只是从局部上进行最优，最后得到一个近似于最优解的结果）

贪心算法容易和动态规划搞混，我对他们也容易搞混，我是这么区分他们的：

• 动态规划

1. 整体问题的最优解依赖各个子问题的最优解
2. 需要记录以前的最优解

• 贪心算法

1. 每一步都做到一个贪心的选择
2. 上一步的最优解不做保留

贪心算法基本思路：

1. 把求解的问题分成若干个子问题
2. 对于每一个子问题进行局部最优解的求解
3. 把子问题的最优解整合成这个大问题的解

例题：

假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。

@Test
public void testGiveMoney() {
    //找零钱
    int[] m = {25, 10, 5, 1};
    int target = 99;
    int[] results = giveMoney(m, target);
    System.out.println(target + "的找钱方案:");
    for (int i = 0; i < results.length; i++) {
        System.out.println(results[i] + "枚" + m[i] + "面值");
    }
}
 
public int[] giveMoney(int[] m, int target) {
    int k = m.length;
    int[] num = new int[k];
    for (int i = 0; i < k; i++) {
        num[i] = target / m[i];
        target = target % m[i];
    }
    return num;
}