在算法世界里,有很多著名的算法,貪心算法是其中最常見、使用最廣泛的算法之一。貪心,顧名思義,是貪得無厭、不知足的意思。貪心算法的意思是,在解決問題的每一步中總是做出在當(dāng)前看來最好的選擇,這個過程一直持續(xù)到解題的最后一步。
貪心算法的使用范圍非常廣泛,在很多實際問題中都有應(yīng)用。例如快遞公司寄送快遞、工廠分配物資時,都使用了貪心算法。下面的例題可以幫助同學(xué)們更好地理解貪心算法。
例:安奇奇的背包
春天到了,安奇奇打算外出郊游,吃貨安奇奇想要在背包里裝入盡可能多的零食,但他只能攜帶一個小背包。
只可惜,背包的容量有限,所以安奇奇需要謹(jǐn)慎地選擇將哪些零食放入背包?,F(xiàn)在,擺在安奇奇面前的有4種零食,分別是巧克力、薯片、辣條和牛肉干。這4種零食的體積和價值如下圖:
安奇奇的背包容量為8,他應(yīng)該選擇將哪幾種零食放入背包,才能使得背包中的零食總價值最高呢?
A.巧克力、薯片、辣條
B. 辣條、牛肉干
C.薯片、辣條、牛肉干
答案:A
解析:這是貪心算法里最常見的一類題型,名叫“背包問題”。因為背包的容量有限,所以安奇奇不可能把所有零食都塞到背包里。這個時候,最好的解題策略是先算出每種零食的性價比,再選擇性價比更高的零食放入背包。性價比可以用“價值÷體積”算出來。
巧克力的性價比:12.50÷2.50=5.00
薯片的性價比:9.51÷3.17=3.00
辣條的性價比:5.61÷1.10≈5.10
牛肉干的性價比:15.00÷5.00=3.00
再比較4種零食的性價比:5.10gt;5.00gt;3.00=3.00
因此,安奇奇就可以按照以下步驟把零食裝入背包:
空背包
第1步:裝入性價比最高的辣條。
第2步:裝入性價比第2高的巧克力。
第3步:薯片和牛肉干的性價比相同,但牛肉干體積更大,無法裝入背包,故選擇薯片。
計算思維訓(xùn)練
安奇奇選擇合適的零食放入背包的過程就用到了貪心算法。貪心算法就是在每一步都做出最佳的選擇,希望最后能夠得到最好的結(jié)果。
練一練:
吃貨安奇奇面前擺著36個一模一樣的正方形餅干盒,所有的餅干盒大小都一樣,排成6×6的正方形,上面寫著數(shù)字。這些數(shù)字是這盒餅干的價格。數(shù)字越大,餅干的價格越貴。
現(xiàn)在,安奇奇可以從中選擇6盒餅干,如果規(guī)定每行只能選一盒餅干,且選擇的餅干總價不超過460,安奇奇的最佳選擇方案是什么呢?
課堂內(nèi)外·小學(xué)版(智慧數(shù)學(xué))2024年5期