8000 fix Grokking-Algorithms · dryyun/algorithms-note@9cca871 · GitHub
[go: up one dir, main page]
Skip to content

Commit 9cca871

Browse files
dryyundryyun
committed
fix Grokking-Algorithms
1 parent 95d7881 commit 9cca871

File tree

3 files changed

+15
-11
lines changed

3 files changed

+15
-11
lines changed

‎Grokking-Algorithms/chapter9/9.1.js

Lines changed: 13 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -7,30 +7,32 @@ const util = require('../../util.js');
77

88
let weights = 4;
99
let entities = {
10-
'a': {'p': 3000, 'w': 4},
11-
'b': {'p': 2000, 'w': 3},
12-
'c': {'p': 1500, 'w': 1},
13-
'd': {'p': 2000, 'w': 1},
10+
'a': {'p': 3000, 'w': 4}, // 音响，价值 3000，重量 4
11+
'b': {'p': 2000, 'w': 3}, // 笔记本电脑
12+
'c': {'p': 1500, 'w': 1}, // 吉他
13+
'd': {'p': 2000, 'w': 1}, // iPhone
1414
};
1515

1616
let result = {
1717
'undef': util.fillArray(weights + 1)
1818
};
1919

20-
Object.keys(entities).forEach(k => {
20+
let keys = Object.keys(entities);
21+
let keysLen = keys.length;
22+
23+
keys.forEach(k => {
2124
result[k] = util.fillArray(weights + 1);
2225
});
2326

24-
let keys = Object.keys(entities);
25-
2627
let preK = 'undef';
27-
for (let k = 0; k < keys.length; k++) {
28+
let max = 0;
29+
for (let k = 0; k < keysLen; k++) {
2830
let key = keys[k];
2931
for (let w = 1; w <= weights; w++) {
3032
let last = result[preK][w];
3133
if (entities[key]['w'] <= w) {
3234
let now = entities[key]['p'] + result[preK][w - entities[key]['w']];
33-
result[key][w] = Math.max(now, last);
35+
result[key][w] = max = Math.max(now, last);
3436
} else {
3537
result[key][w] = last;
3638
}
@@ -39,3 +41,5 @@ for (let k = 0; k < keys.length; k++) {
3941
}
4042

4143
console.log(result);
44+
console.log('最大价值', max);
45+

‎Grokking-Algorithms/chapter9/9.3.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ function lcs(wordA, wordB) {
2828
}
2929
}
3030
return {
31-
lcs: lcs,
31+
lcs,
3232
offset: lastSubIndex - lcs + 1,
3333
sequence: wordA.slice(lastSubIndex - lcs + 1, lastSubIndex + 1)
3434
};

‎Grokking-Algorithms/chapter9/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88

99
> 动态规划，先解决子问题，在逐步解决大问题
1010
> 仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用
11-
> 要设计出动态规划解决方案可能很难
11+
> 要设计出动态规划解决方案很难
1212
1313
![背包问题](./beibao.jpg)
1414

0 commit comments

Comments
 (0)
0