“貪心”的算法

在算法世界里，有很多著名的算法，貪心算法是其中最常見、使用最廣泛的算法之一。貪心，顧名思義，是貪得無厭、不知足的意思。貪心算法的意思是，在解決問題的每一步中總是做出在當前看來最好的選擇，這個過程一直持續到解題的最后一步。

貪心算法的使用范圍非常廣泛，在很多實際問題中都有應用。例如快遞公司寄送快遞、工廠分配物資時，都使用了貪心算法。下面的例題可以幫助同學們更好地理解貪心算法。

例：安奇奇的背包

春天到了，安奇奇打算外出郊游，吃貨安奇奇想要在背包里裝入盡可能多的零食，但他只能攜帶一個小背包。

只可惜，背包的容量有限，所以安奇奇需要謹慎地選擇將哪些零食放入背包。現在，擺在安奇奇面前的有4種零食，分別是巧克力、薯片、辣條和牛肉干。這4種零食的體積和價值如下圖：

安奇奇的背包容量為8，他應該選擇將哪幾種零食放入背包，才能使得背包中的零食總價值最高呢？

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

因此，安奇奇就可以按照以下步驟把零食裝入背包：