贪心算法

首页 » 算法 » 贪心算法

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

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

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

  • 动态规划
  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;
}

分享到:
赞(0) 打赏

评论 3

评论前必须登录!

 

  1. #1

    挺明白的

    我是你哥2个月前 (05-26)
  2. #2

    看了那么多博客,就你的能看懂

    我是你哥2个月前 (05-26)
  3. #3

    可以的

    匿名3天前

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00

      登陆功能正在开发中...

      请您使用第三方帐号快捷登录

      Q Q 登 录
      微 博 登 录