ength - 1; i >= 0; i--) {
const coin = coins[i];
while (total + coin <= amount) {
change.push(coin);
total += coin;
}
}
return change;
}
const result = minCoinChange([1, 5, 10, 25], 36);
console.log(result); // [ 25, 10, 1 ]
前提是coins数组已经按从小到大排好序了，贪心算法从最大值开始尝试，如果该值不满足条件（要找零的钱数），则继续向下找，直到找到满足条件的所有值。以上算法并不能满足所有情况下找出最优方案，例如下面这种情况：
const result = minCoinChange([1, 2, 5, 9, 10], 18);
console.log(result); // [ 10, 5, 2, 1 ]
给出的结果[10, 5, 2, 1]并不是最优方案，最优方案应该是[9, 9]。
与动态规划相比，贪心算法更简单、效率更高。但是其结果并不总是最理想的。但是综合看来，它相对执行时间来说，输出一个可以接受的结果。
背包问题
| 物品# |
重量 |
价值 |
| 1 |
2 |
3 |
| 2 |
3 |
4 |
| 3 |
4 |
5 |
在动态规划的例子里，假定背包的容量为5，最佳方案是往背包里装入物品1和物品2，总价值为7。在贪心算法中，我们需要考虑分数的情况，假定背包的容量为6，装入物品1和物品2之后，剩余容量为1，可以装入1/4的物品3，总价值为3+4+0.25×5=8.25。我们来看看具体的实现代码：
function knapSack(capacity, weights, values) {
const n = values.length;
let load = 0;
let val = 0;
for (let i = 0; i < n && load < capacity; i++) {
if (weights[i] <= capacity - load) {
val += values[i];
load += weights[i];
console.log(`物品${i + 1}，重量：${weights[i]}，价值：${values[i]}`);
} else {
const r = (capacity - load) / weights[i];
val += r * values[i];
load += weights[i];
console.log(`物品${i + 1}的${r}，重量：${r * weights[i]}，价值：${val}`);
}
}
return val;
}
从第一个物品开始遍历，如果总重量小于背包的容量，则继续迭代，装入物品。如果物品可以完整地装入背包，则将其价值和重量分别计入到变量val和load中，同时打印装入物品的信息。如果物品不能完整地装入背包，计算能够装入的比例r，然后将这个比例所对应的价值和重量分别计入到变量val和load中，同时打印物品的信息。最终输出总的价值val。下面是测试结果：
const capacity = 6;
const weights = [2, 3, 4];
const values = [3, 4, 5];
console.log(knapSack(capacity, weights, values));
物品1，重量：2，价值：3
物品2，重量：3，价值：4
物品3的0.25，重量：1，价值：8.25
8.25
在动态规划算法中，如果将背包的容量也设定为6，计算结果则为8。
最长公共子序列（LCS）
最后我们再来看看如何用贪心算法解决LCS的问题。下面的代码返回了两个给定数组中的LCS的长度：
function lcs(wordX, wordY, m = wordX.length, n = wordY.length) {
if (m === 0 || n === 0) {
return 0;
}
if (wordX[m - 1] === wordY[n - 1]) {
return 1 + lcs(wordX, wordY, m - 1, n - 1);
}
const a = lcs(wordX, wordY, m, n - 1);
const b = lcs(wordX, wordY, m - 1, n);
return a > b ? a : b;
}
const wordX = ['a', 'c', 'b', 'a', 'e', 'd'];
const wordY = ['a', 'b', 'c', 'a', 'd', 'f'];
console.log(lcs(wordX, wordY)); // 4