(Greedy)贪心策略

贪心策略是一种每一步都采取当前状态下最优的选择(局部最优解)，从而希望推导出全局最优解的一种策略。
在我们之前文章里讲到的算法中，最小生成树算法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