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