美文网首页
(Greedy)贪心策略

(Greedy)贪心策略

作者: Bel李玉 | 来源:发表于2020-08-23 18:17 被阅读0次

贪心策略是一种每一步都采取当前状态下最优的选择(局部最优解),从而希望推导出全局最优解的一种策略。
在我们之前文章里讲到的算法中,最小生成树算法Prim、Kruskal和最短路径算法Dijjstra都是采用的贪心策略。下面我们通过探讨一下几个问题来了解贪心策略。

问题1-最优装载问题

Q1:在北美洲东南部,有一片神秘的海域,是海盗最活跃的加勒比海。

  • 有一天,海盗们截获了一艘装满各种各样古董的货船,每一件古董都价值连城,一旦打碎就失去了它的价值。
  • 海盗船的载重量为W,每件古董的重量为Wi,海盗们该如何把尽可能多数量的古董装上海盗船?
  • 比如 W 为 30,wi分别为 3、5、4、10、7、14、2、11
分析

贪心策略:每次都选择重量最小的古董
1,选择重量为2的古董,剩承重为 28。
2,选择重量为3的古董,剩承重为 25。
3,选择重量为4的古董,剩承重为 21。
4,选择重量为5的古董,剩承重为 16。
5,选择重量为7的古董,剩承重为 9。
当第5步时,载重船已经不足以在多装载一个古董了。最终总载数量为 5。

实现

我们新建一个 Greedy

class Greedy {
    static func bestLoadSolution(_ weights: [Int], _ capacity: Int) -> Int{
        var weightArray = weights
        var count = 0
        var weight = 0
        weightArray.sort() // 1

        for newWeight in weights {
            if (newWeight + weight < capacity) { // 2
                weight += newWeight
                count += 1
            }
        }
        return count // 3
    }
}
  • 1,将weights数组按照从小到大的顺序进行排序。
  • 2,如果当前总重量和即将装载的数量不超过总容量,则将其装到船上。
  • 3,返回装载的总数量。

问题2-零钱兑换

Q2:假设有 25分、10分、5分、1分的硬币,现要找给顾客41分的零钱,如何办到硬币个数最少?

分析

贪心策略:每一次都选择面值最大的硬币
1,选择25分的硬币,剩 16分。
2,选择10分的硬币,剩 6 分。
3,选择5分的硬币,剩 1 分。
4,选择1分的硬币,剩 0 分,找零完成。
最终的解是共4枚硬币:
25分、10分、5分、1分硬币各一枚。

实现

我们在Greedy类中,增加以下类方法:

    static func coinChange(_ coins: [Int], _ changeNum: Int) -> [Int] {
        var changeCoins = [Int]()
        var exchangeCoin = coins

        var newChangeNum = changeNum

        exchangeCoin.sort { (coin1,coin2 ) -> Bool in // 1
            return coin1 > coin2
        }

        for coin in exchangeCoin { // 2
            while coin <= newChangeNum { // 3
                changeCoins.append(coin)
                newChangeNum -= coin
            }
        }
        return changeCoins
    }
  • 1,对可用的零钱进行从大到小排序。
  • 2,对可用零钱进行遍历。
  • 3,如果零钱值小于需找零的钱,则将其放入数组。
测试

我们新建一个单元测试:

    func testChangeCoin(){
        let coins = [25, 5, 10, 1]
        let totalMoney = 41
        let exchangeCoins = Greedy.coinChange(coins, totalMoney)
        print(exchangeCoins)


        let anotherCoins = [25, 20, 5, 1]

        let anotherExchangeCoins = Greedy.coinChange(anotherCoins, totalMoney)
        print(anotherExchangeCoins)

        XCTAssert(exchangeCoins == [25, 10, 5 ,1] && anotherExchangeCoins == [25, 5, 5, 5, 1])
    }

在测试过程中我们可以看出,当我们将可用零钱替换为 [25, 20, 5, 1] 时,根据贪婪策略得到的找零方案为 [25, 5, 5, 5, 1] 即 1 个 25分,3个5分,1个1分的。但在这种情况下,最优的找零方案应该为[20, 20, 1 ]即 2 个20 的,1个1分的。由此我们可以知道,局部最优并不能保证全局最优,在贪婪策略中,注重局部利益最大化,没有测试所有可能的解,容易过早做决定,所以没法达到最佳解。

最后附上本文的相关代码DataAndAlgorim

相关文章

  • 数据结构第二季 Day16 贪心、分治

    一、贪心(Greedy) 1、什么是贪心策略?经典应用有哪些(至少说两个)? 贪心策略,也称为贪婪策略。 每一步都...

  • (Greedy)贪心策略

    贪心策略是一种每一步都采取当前状态下最优的选择(局部最优解),从而希望推导出全局最优解的一种策略。在我们之前文章里...

  • 26-贪心(Greedy)

    贪心(Greedy) 贪心策略:也称为贪婪差略 使用贪心策略,在执行每一步的过程中,都会选择当前状态下的最优解(局...

  • 【恋上数据结构与算法二】(六)贪心(Greedy)

    贪心(Greedy) ◼ 贪心策略,也称为贪婪策略每一步都采取当前状态下最优的选择(局部最优解),从而希望推导出全...

  • 爬山&退火算法-产品经理数学课(4)

    关键词:爬山算法、模拟退火算法、蒙特卡洛思想、贪心、Greedy策略、Metropolis准则 上古法师张忒柱的故...

  • 程序设计的16种类型

    Dynamic Programming(动态规划) Greedy(贪心算法) Complete Search(穷举...

  • 每日英汉对照(212-9-14)

    1 Don’t get greedy. 做人不能太贪心。 2 You are only working here ...

  • 算法理论 | 贪心算法

    贪心算法 贪心算法,又称贪婪算法(Greedy Algorithm),是指在对问题求解时,总是做出在当前看来是最好...

  • 《数据结构与算法之美》31——贪心算法

    什么是贪心算法 贪心算法(英语:greedy algorithm),又称贪婪算法,是一种在每一步选择中都采取在当前...

  • 2021-08-25

    【开言小挑战】人总是贪心的,往往会想要的越来越多。可鱼与熊掌怎么能兼得? greedy: 贪心You can't ...

网友评论

      本文标题:(Greedy)贪心策略

      本文链接:https://www.haomeiwen.com/subject/vqtwjktx.html