貪心算法遵循一種近似解決問題的技術，期盼通過每個階段的局部最優選擇（當前最好的解），從而達到全局的最優（全局最優解）。它不像動態規划算法那樣計算更大的格局。
我們來看看如何用貪心算法解決11.2節中的最少硬幣找零問題和背包問題。
我們在第9章介紹了一些其他的貪心算法，比如Dijkstra算法、Prim算法和Kruskal算法。
11.3.1 最少硬幣找零問題
最少硬幣找零問題也能用貪心算法解決。大部分情況下的結果是最優的，不過對有些面額而言，結果不會是最優的。
來看看算法：
function MinCoinChange(coins){
var coins = coins; //{1}
this.makeChange = function(amount) {
var change = ,
total = 0;
for (var i=coins.length; i>=0; i--){ //{2}
var coin = coins[i];
while (total + coin <= amount) { //{3}
change.push(coin); //{4}
total += coin; //{5}
}
}
return change;
};
}
不得不說貪心版本的MinCoinChange比動態規劃版本的簡單多了。和動態規劃方法相似，我們傳遞面額參數，實例化MinCoinChange（行{1}）。
對每個面額（行{2}——從大到小），把它的值和total相加後，total需要小於amount（行{3}）。我們會將當前面額coin添加到結果中（行{4}），也會將它和total相加（行{5}）。
如你所見，這個解法很簡單。從最大面額的硬幣開始，拿盡可能多的這種硬幣找零。當無法再拿更多這種價值的硬幣時，開始拿第二大價值的硬幣，依次繼續。
用和DP方法同樣的測試代碼測試：
var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
console.log(minCoinChange.makeChange(36));
結果依然是[25, 10, 1]，和用DP得到的一樣。下圖闡釋了算法的執行過程：
然而，如果用[1, 3, 4]面額執行貪心算法，會得到結果[4, 1, 1]。如果用動態規劃的解法，會得到最優的結果[3, 3]。
比起動態規划算法而言，貪心算法更簡單、更快。然而，如我們所見，它並不總是得到最優答案。但是綜合來看，它相對執行時間來說，輸出了一個可以接受的解。
11.3.2 分數背包問題
求解分數背包問題的算法與動態規劃版本稍有不同。在0-1背包問題中，只能向背包裡裝入完整的物品，而在分數背包問題中，我們可以裝入分數的物品。我們用前面用過的例子來比較兩者的差異，如下所示：
物品#
重量
價值
1
2
3
2
3
4
3
4
5
在動態規劃的例子裡，我們考慮背包能夠攜帶的重量只有5。而在這個例子裡，我們可以說最佳解決方案是往背包裡裝入物品1和物品2，總重量為5，總價值為7。
如果在分數背包問題中考慮相同的容量，得到的結果是一樣的。因此，我們考慮容量為6的情況。
在這種情況下，解決方案是裝入物品1和物品2，還有25%的物品3。這樣，重量為6的物品總價值為8.25。
我們來看看下面這個算法：
function knapSack(capacity, values, weights) {
var n = values.length,
load = 0, i = 0, val = 0;
for (i = 0; i < n && load < capacity; i++) { //{1}
if (weights[i] <= (capacity - load)) { //{2}
val += values[i];
load += weights[i];
} else {
var r = (capacity - load) / weights[i]; //{3}
val += r * values[i];
load += weights[i];
}
}
return w;
}
下面是對算法的解釋。
行
{1}：總重量少於背包容量，繼續迭代，裝入物品。行
{2}：如果物品可以完整地裝入背包，就將其價值和重量分別計入背包已裝入物品的總價值（val）和總重量（load）。行
{3}：如果物品不能完整地裝入背包，計算能夠裝入部分的比例（r）。
如果在0-1背包問題中考慮同樣的容量6，我們就會看到，物品1和物品3組成了解決方案。在這種情況下，對同一個問題應用不同的解決方法，會得到兩種不同的結果。