|
{
kS[i][w] = kS[i - 1][w];
}
}
}
console.log(kS);
}
对于const a，其价值分为两部分，第一部分就是它自己的价值（values[i - 1]），第二部分是用背包剩余的重量（w - weights[i - 1]）装进前一个物品（kS[i - 1]）。对于const b，就是找前一个能放入这个重量的物品（kS[i - 1][w]）。然后取这两种情况下的最大值。
测试一下knapSack()函数，
const capacity = 5;
const weights = [2, 3, 4];
const values = [3, 4, 5];
knapSack(capacity, weights, values, weights.length);
下面是矩阵kS的输出结果：
[
[ 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 3, 3, 3, 3 ],
[ 0, 0, 3, 4, 4, 7 ],
[ 0, 0, 3, 4, 5, 7 ]
]
最长公共子序列（LCS）
找出两个字符串序列的最长子序列的长度。所谓最长子序列，是指两个字符串序列中以相同顺序出现，但不要求连续的字符串序列。例如下面两个字符串：
字符串1：acbaed
字符串2：abcadf
则LCS为acad。
和背包问题的思路类似，我们用下面的表格来描述整个过程：
| |
|
a |
b |
c |
a |
d |
f |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| a |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
| c |
0 |
1 |
1 |
2 |
2 |
2 |
2 |
| b |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
| a |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
| e |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
| d |
0 |
1 |
2 |
2 |
3 |
4 |
4 |
矩阵的第一行和第一列都被设置为0，剩余的部分，遵循下面两种情况：
- 如果wordX[i - 1]和wordY[j - 1]相等，则矩阵对应的单元格的值为单元格[i - 1][j - 1]的值加1。
- 如果wordX[i - 1]和wordY[j - 1]不相等，则找出单元格[i - 1][j]和单元格[i][j - 1]之间的最大值。
下面是具体的实现代码：
function lcs(wordX, wordY) {
const m = wordX.length;
const n = wordY.length;
const l = [];
for (let i = 0; i <= m; i++) {
l[i] = [];
for (let j = 0; j <= n; j++) {
l[i][j] = 0;
}
}
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i === 0 || j === 0) {
l[i][j] = 0;
} else if (wordX[i - 1] === wordY[j - 1]) {
l[i][j] = l[i - 1][j - 1] + 1;
} else {
const a = l[i - 1][j];
const b = l[i][j - 1];
l[i][j] = Math.max(a, b);
}
}
}
console.log(l);
console.log(l[m][n]);
}
我们将矩阵打印出来，结果如下：
const wordX = ['a', 'c', 'b', 'a', 'e', 'd'];
const wordY = ['a', 'b', 'c', 'a', 'd', 'f'];
lcs(wordX, wordY);
[
[ 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 1, 1, 1, 1, 1, 1 ],
[ 0, 1, 1, 2, 2, 2, 2 ],
[ 0, 1, 2, 2, 2, 2, 2 ],
[ 0, 1, 2, 2, 3, 3, 3 ],
[ 0, 1, 2, 2, 3, 3, 3 ],
[ 0, 1, 2, 2, 3, 4, 4 ]
]
4
矩阵中最后一个单元格的值为LCS的长度。那如何计算出LCS的具体内容呢？我们可以设计一个相同的solution矩阵，用来做标记，如果wordX[i - 1]和wordY[j - 1]相等，则将solution矩阵中对应的值设置为'diagonal'，即上面表格中背景为灰色的单元格。否则，根据[i][j]和[i - 1][j]是否相等标记为'top'或'left'。然后通过printSolution()方法来找出LCS的内容。修改之后的代码如下：
function printSolution(solution, wordX, m, n) {
let a = m;
let b = n;
let x = solution[a][b];
let answer = '';
while (x !== '0') {
if (solution[a][b] === 'diagonal') {
answer = wordX[a - 1] + answer;
a--;
b--;
} else if (solution[a][b] === 'left') {
b--;
} else if (solution[a][b] === 'top') {
a--;
}
x = solution[a][b];
}
return answer;
}
function lcs(wordX, wordY) {
const m = wordX.length;
const n = wordY.length;
const l = [];
const solution = [];
for (let i = 0; i <= m; i++) {
l[i] = [];
solution[i] = [];
for (let j = 0; j <= n; j++) {
l[i][j] = 0;
solution[i][j] = '0';
}
}
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i === 0 || j === 0) {
l[i][j] = 0;
} else if (wordX[i - 1] === wordY[j - 1]) {
l[i][j] = l[i - 1][j - 1] + 1;
solution[i][j] = 'diagonal';
} else {
const a = l[i - 1][j];
const b = l[i][j - 1];
l[i][j] = Math.max(a, b);
solution[i][j] = l[i][j] === l[i - 1][j] ? 'top' : 'left';
}
}
}
return printSolution(solution, wordX, m, n);
}
测试结果：
const wordX = ['a', 'c', 'b', 'a', 'e', 'd'];
const wordY = ['a', 'b', 'c', 'a', 'd', 'f'];
console.log(lcs(wordX, wordY)); // acad
贪心算法
贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择，从而达到全局的最优。它不像动态规划算法那样计算更大的格局。
最少硬币找零
我们来看看如何用贪心算法解决前面提到过的最少硬币找零问题。
function minCoinChange(coins, amount) {
const change = [];
let total = 0;
for (let i = coins.l |