(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
