weijieblog / blog Goto Github PK
View Code? Open in Web Editor NEW技术博客
技术博客
很多人小时候都听过这样一个故事:
“从前有座山,山里有座庙,庙里有个老和尚他在讲故事,他说:从前有座山,山里有个庙,庙里有个老和尚他在讲故事,他说:……”
现在我们把这个故事写成 javascript 程序,这就是一个递归的程序:
var story = function () {
var content = '从前有座山,山里有座庙,庙里有个老和尚他在讲故事,他说:'
return content + story()
}
我们都知道,如果把这个故事讲下去,从一到那由他,到恒河沙,到无量大数,到永恒尽头也不会有结局 。一样的,如果我们运行上面的代码,程序就会进入一种无尽的轮回,生生世世,直到栈溢出抛出 Uncaught RangeError: Maximum call stack size exceeded(…)
也不会有返回值。
在永恒的时空中,无尽的轮回被认为是一种很自然的存在。但是,程序中我们把这种无尽的递归称为死递归,它是一种和死循环一样的荒谬存在。就像所有循环的程序都会有一个退出条件一样,对于每一个递归的程序,也都会有一个退出条件,加入退出条件后,我们的 story
函数就成了这样:
var story = function (times) {
if (times > 0) {
var content = '从前有座山,山里有座庙,庙里有个老和尚他在讲故事,他说:'
return content + story(--times)
} else {
return '(未完待续...)'
}
}
如此一来,调用 story(3)
就能够将故事重复三次。到此,我们完成了一个递归的程序,用来讲述一个耳熟能详的递归的故事。
说到递归的应用,往往会让人联想到 快速排序
和 遍历二叉树
等难懂的算法,而让许多新手闻之色变。但其实,递归作为一种轮回,也可以用来解决常见的编程问题,比如迭代。甚至在函数式编程的流派里面,迭代本来就应该是递归的。
接下来我们使用递归来编写 javascript 中常用的 forEach
map
filter
函数。在写那几个函数之前,我们先来定义几个辅助函数。
// 得到 array 的第一个元素
// head([1,2,3,4,5])
// => 1
var head = function (array) {
return array[0]
}
// 得到 array 除第一个元素外的其他元素
// tail([1,2,3,4,5])
// => [2,3,4,5]
var tail = function (array) {
return array.slice(1, array.length)
}
OK,准备工作已经完成,现在我们用递归的方法实现第一个函数 forEach
。这个函数接受两个参数,第一个参数是数组,第二个参数是一个函数。执行 forEach
时会遍历作为第一个参数的数组,并且逐个将数组中的成员作为参数传给 fn 函数执行。
// forEach([1,2,3], function (x) { console.log(x) })
// => 1
// => 2
// => 3
var forEach = function (array, fn) {
if (array.length > 0) {
fn(head(array))
forEach(tail(array), fn)
}
}
现在是 map
函数。这个函数接受两个参数,第一个参数是数组,第二个参数是一个函数。执行 map
时会遍历作为第一个参数的数组,并且逐个将数组中的成员作为参数传给 fn 函数执行,然后将 fn 的返回值逐个装入新数组,最后返回新数组。
// map([1,2,3], function (x) { return x+1 })
// => [2,3,4]
var map = function (array, fn) {
if (array.length > 0) {
return [fn(head(array))].concat(map(tail(array), fn))
} else {
return []
}
}
最后一个是 filter
函数。 这个函数接受两个参数, 第一个参数是数组,第二个参数是一个函数。执行 filter
时会遍历作为第一个参数的数组,并且逐个将数组中的成员作为参数传给 fn 函数执行,如果 fn 的返回值是 true 则将当前参数装入新数组,否则忽略当前参数,最后返回新数组。
// filter([1,2,3,4,5], function (x) { return x>2 })
// => [3,4,5]
var filter = function (array, fn) {
if (array.length > 0) {
if (fn(head(array)) === true) {
return [head(array)].concat(filter(tail(array), fn))
} else {
return [].concat(filter(tail(array), fn))
}
} else {
return []
}
}
(完)
背包问题是一类非常经典的组合优化问题的统称,我青葱年少时,曾对这个问题着迷。而我企图在百度上搜索这个问题的答案时,被无数数学语言弄得差点连问题都看不懂。尽管数学是美的,但为了不让大家叉掉我的博客。我将换种方式来描述这个问题,那么,这个问题就变成了老板请吃饭问题
。
很久很久以前,有一个如你我般忠厚善良的可爱码农,在连续加班大半年以后,老板终于看到了他人性的光辉,决定请他吃晚餐。下班后,他们来到一个餐馆,餐馆的服务员给了他们如下一份菜单,老板让码农随意点菜,但不要重复点。而他们只能吃下 30 两重的东西,多吃一两都会胃炸裂而亡。那么问题来了,这位可爱的码农在不吃死的情况下,最多能花掉老板多少钱,如何点菜可以到达这个数目呢?
// 以下是他们所能吃的东西的上限和菜单
var capacity = 30,
collections = [
{name: '米饭' , weight: 7, price: 10},
{name: '宫保鸡丁' , weight: 6, price: 40},
{name: '紫菜蛋花汤' , weight: 12, price: 30},
{name: '水煮牛肉' , weight: 10, price: 50},
{name: '海鲜蒸蛋' , weight: 8, price: 35},
{name: '炭烤生蚝' , weight: 2, price: 40},
{name: '白灼时蔬' , weight: 5, price: 30}
]
码农看着菜单思索,由于连续加班太久,一下想不出好的法子,突然他的第二人格冒出来跟他说,快用贪心法!
贪心法跟其他解决此类问题的算法比起来,是一种速度很快的算法,缺点就是它未必总能得到最优解。但由于其速度快而且简单,在很多地方还是很讨喜的。
贪心法的一般求解步骤:
在这里问题是 如何点菜可以让老板花更多的钱
,子问题就是 这道菜我该不该点
。有了这样的一个子问题码农就可以遍历整个菜单,对着菜单上面的每一个菜做点或是不点的判断了。
而贪心策略在这个问题里有三种选择:
直觉告诉他,第三种策略比较容易让老板多掏钱,于是他采用第三种策略。
那么程序的流程就出来了:
// 以下是他们所能吃的东西的上限和菜单
var capacity = 30,
collections = [
{name: '米饭' , weight: 7, price: 10},
{name: '宫保鸡丁' , weight: 6, price: 40},
{name: '紫菜蛋花汤' , weight: 12, price: 30},
{name: '水煮牛肉' , weight: 10, price: 50},
{name: '海鲜蒸蛋' , weight: 8, price: 35},
{name: '炭烤生蚝' , weight: 2, price: 40},
{name: '白灼时蔬' , weight: 5, price: 30}
]
var knapsackProblemByGreedy = function (collections, capacity, sortBy) {
// 获得排好序的菜单
var collections = sortBy(collections),
result = {
totalPrice: 0,
totalWeight: 0,
selected: []
},
currentWeight = 0 // 记录已点的菜的总重量
// 遍历排好序的菜单
collections.forEach(function (collection) {
var temp = currentWeight + collection.weight
// 如果点下当前的菜,菜的重量总和会超过两人的饭量总和(capacity)的值
// 则程序不会进入下面的 if 语句去修改结果(result)的值
currentWeight = temp <= capacity ? temp : currentWeight
if (currentWeight === temp) {
result.totalPrice += collection.price
result.totalWeight += collection.weight
result.selected.push(collection)
}
})
return result
}
// 将菜单按照性价比排序
var sortByCostPerformance = function (collections) {
// 这里的 slice(0) 是希望生成一个排序后的副本,而不是在原来的数组上做排序操作
return collections.slice(0).sort(function (a, b) {
return (b.price / b.weight) - (a.price / a.weight)
})
}
console.log(knapsackProblemByGreedy(collections, capacity, sortByCostPerformance))
运行上面的代码就可以在控制台中看到结果,如果喜欢,可以把其他两种贪婪策略应用到程序中,看看不同的策略会对程序照成何种影响(完)。
之前的博文介绍了如何利用 Levenshtein distance 算法求解从一个字符串到另外一个字符串的编辑距离。在博文的结尾提到了一种通过回溯 Levenshtein distance 算法生成的表格,求得从一个字符串到另外一个字符串变化步骤的算法,算法有如下效果。
diff('saturday', 'sunday')
/* output
[{
content: 'n',
index: 4,
type: 'UPDATE'
}, {
content: 't',
index: 2,
type: 'REMOVE',
}, {
content: 'a',
index: 1,
type: 'REMOVE',
}]
*/
在之前的博文中,levenshteinDistance 函数将 matrix 的最后一个单元格的值返回,而这里所说的 levenshteinDistance 填满的表格,指的是整个 matrix 。
注释部分表示算法输出的结果,输出的数组表示:
saturday
中 index 为 4 的字符替换为 n。(即 r 替换为 n)saturday
中 index 为 2 的字符删除。(即删除 t)saturday
中 index 为 1 的字符删除。(即删除 a)之前的博文通过自底向上法完成了一个表格,如下:
- | - | s | a | t | u | r | d | a | y |
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
u | 2 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 |
n | 3 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 6 |
d | 4 | 3 | 3 | 3 | 3 | 4 | 3 | 4 | 5 |
a | 5 | 4 | 3 | 4 | 4 | 4 | 4 | 3 | 4 |
y | 6 | 5 | 4 | 4 | 5 | 5 | 5 | 4 | 3 |
既然是回溯,那么就要从这个表格的最后一个单元格出发,按照一定的路径向第一个单元格移动,即从右下角向左上角移动。在这里,如何选择回溯的路径将是这个算法成功的关键。Levenshtein distance 的数学定义描述了每个单元格的值都是根据其左边的单元格,左上方的单元格,上方的单元格的值的关系确定的,具体的确定方式可以看之前的博文。同样的我们在回溯的时候也要考虑当前单元格和其左边的单元格,左上方的单元格,上方的单元格的值的关系。图例如下:
- | - | s | a | t | u | r | d | a | y |
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
u | 2 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 |
n | 3 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 6 |
d | 4 | 3 | 3 | 3 | 3 | 4 | 3 | 4 | 5 |
a | 5 | 4 | 3 | 4 | 4 | 4 | 4 | 3 (leftOver) | 4 (over) |
y | 6 | 5 | 4 | 4 | 5 | 5 | 5 | 4 (left) | 3 (origin) |
起点 origin
可以往 left
方向, leftOver
方向, over
方向出发。但我们的目的既然是求解从一个字符串到另外一个字符串最少编辑的步骤,那么在选择方向的时候得满足两点。
left
, leftOver
和 over
中编辑距离(也就是值)最小的方向出发。leftOver
方向出发。关于第 2 点,是因为
leftOver
方向代表了更改或是不操作, 而left
和over
则分别代表删除和插入,一次删除加一次插入的效果才相当于一次更改,所以优先选择更改编辑成本较小。而不操作没有编辑成本。移动的方向和其编辑操作的关系,下个小节会说明。
根据这两条规则,很快就可以确定回溯的路径,如下,加粗字体表示回溯时会走的路径:
- | - | s | a | t | u | r | d | a | y |
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
u | 2 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 |
n | 3 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 6 |
d | 4 | 3 | 3 | 3 | 3 | 4 | 3 | 4 | 5 |
a | 5 | 4 | 3 | 4 | 4 | 4 | 4 | 3 | 4 |
y | 6 | 5 | 4 | 4 | 5 | 5 | 5 | 4 | 3 |
在回溯的路径上,单元格里边的数字每发生一次变化,就代表发生了一次编辑操作,比如。
- | - | s | a | t | u | r | d | a | y |
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s | 1 | 0(1,1) | 1(2,1) | 2(3,1) | 3 | 4 | 5 | 6 | 7 |
u | 2 | 1 | 1 | 2 | 2(4,2) | 3 | 4 | 5 | 6 |
n | 3 | 2 | 2 | 2 | 3 | 3(5,3) | 4 | 5 | 6 |
d | 4 | 3 | 3 | 3 | 3 | 4 | 3 | 4 | 5 |
a | 5 | 4 | 3 | 4 | 4 | 4 | 4 | 3 | 4 |
y | 6 | 5 | 4 | 4 | 5 | 5 | 5 | 4 | 3 |
可以看到,路径上数字的变化次数是 3 次,这和我们执行 levenshteinDistance 的结果是一致的。那么每一次变化分别都代表了什么操作呢。可以通过观察数字变化前的单元格([(5,3),(3,1),(2,1)])得出些头绪,如下:
其中
-
后面的是编辑好的字符串,而-
之前的是待编辑的字符串。
// (5,3) :下一步往 `leftOver` 方向走到 (4,2)
// from (5,3)
satur - day
sun - day
// to (4,2)
satu - nday
su - nday
// 可见将 r 改为 n 即可
// (3,1):下一步往 `left` 方向走到 (2,1)
// from (3,1)
sat - unday
s - unday
// to (2,1)
sa - unday
s - unday
// 可见删掉 t 即可
// (2,1):下一步往 `left` 方向走到 (1,1)
// from (2,1)
sa - unday
s - unday
// to (1,1)
s - unday
s - unday
// 可见删掉 a 即可
总结一下,就是:
left
方向走是删除操作。over
方向走是插入操作。leftOver
方向走是更新操作或是不操作,由当前字符决定,比如从 (1,1) 到 (0,0) 就是不操作。我认为是时候贴代码了
// 定义三种编辑方式
var REMOVE = 'REMOVE',
INSERT = 'INSERT',
UPDATE = 'UPDATE'
// 求解从 list1 到 list2 的最小编辑步骤
// 这里的 levenshteinDistance 不再是返回 matrix 的最后一个单元格,而是返回整个 matrix
// diff('saturday', 'sunday', levenshteinDistance('saturday', 'sunday', match))
/* output
[{
content: 'n',
index: 4,
type: 'UPDATE'
}, {
content: 't',
index: 2,
type: 'REMOVE',
}, {
content: 'a',
index: 1,
type: 'REMOVE',
}]
*/
var diff = function (list1, list2, matrix) {
var len1 = list1.length,
len2 = list2.length,
edits = [],
minimus,
current,
over,
left,
leftOver,
x,
y
// 设置最后一个单元格为起点
x = len1
y = len2
current = matrix[x][y]
// 开始回溯
while (x > 0 || y > 0) {
// 路径到达了最左边的一列,就只能往上走,于是出现了要往 list1 开头连续添加元素的情况。
// 例如: def => abcdef 会连续进入下方的 if 三次,每次进入分别插入 c,b,a。
if (x === 0) {
edits.push({type: INSERT, index: x-1, content: list2[y-1]})
y--
continue
}
// 路径到达了最上面的一行,就只能横着往左走,于是出现了要往 list1 开头连续删除元素的情况。
// 例如:abcdef => def 会连续进入下方的 if 三次,每次进入分别删除 c,b,a。
if (y === 0) {
edits.push({type: REMOVE, index: x-1, content: list1[x-1]})
x--
continue
}
// 找到有可能会前往的三个方向的的值
over = matrix[x][y-1]
left = matrix[x-1][y]
leftOver = matrix[x-1][y-1]
// 总是忘三个方向中值最小的方向前进
minimus = Math.min(over, left, leftOver)
switch (minimus) {
// 优先往左上方前进,更新操作或不操作
case leftOver:
// 当值变化,表示有编辑操作发生
if (current > minimus) {
edits.push({type: UPDATE, index: x-1, content: list2[y-1]})
}
current = leftOver
x--
y--
break
// 往上方前进,插入操作
case over:
// 当值变化,表示有编辑操作发生
if (current > minimus) {
edits.push({type: INSERT, index: x-1, content: list2[y-1]})
}
y--
current = over
break
// 往左方前进,删除操作
case left:
// 当值变化,表示有编辑操作发生
if (current > minimus) {
edits.push({type: REMOVE, index: x-1, content: list1[x-1]})
}
x--
current = left
break
}
}
return edits
}
这个 diff 函数,除了可以用来比较以外还可以用来比较列表,像下面一样。
diff(['jquery', 'reactjs', 'redux', 'require'], ['jquery', 'react', 'reflux', 'webpack', 'elm'],
levenshteinDistance(['jquery', 'reactjs', 'redux', 'require'], ['jquery', 'react', 'reflux', 'webpack', 'elm'], match))
另外,通过自定义的 match
函数(见之前的博文),它可以用来比较更多的东西,比如嵌套的数组。如果你乐意,这个 diff 函数也可以扩写为比较 DOM 树的函数,就像 React 的那个一样。
当然,这个 diff 方法还有很多不完善的地方,比如:
diff('saturday', 'sunday', levenshteinDistance('saturday', 'sunday', match))
这样的接口,实在算不上优美,另外,它也没经过太多的优化。
当我们拼写错 Git 命令的时候,Git 会把相似的命令提供给我们候选,比如我们输入了 statuus
命令
bash
git statuus
git: 'statuus' is not a git command. See 'git --help'.
Did you mean this?
status
Git 会问我们是不是想要输入 `status` ,那么问题来了, Git 作为一个程序,它是通过什么来判断像 `statuus` 和 `status` 这样的两个字符串是否相似的呢。这就是我今天要介绍的 Levenshtein distance 算法啦。
## 求解编辑距离的 Levenshtein distance 算法 [Wiki](https://en.wikipedia.org/wiki/Levenshtein_distance)
这个算法的目的是求出把字符串 A 改为字符串 B 所需要的最少步骤数。比如把 `statuus` 改为 `status` 只用删掉其中的一个 `u` 就好,只用改动一次。定义 levenshteinDistance 函数为该算法的 Javascript 实现,那么 levenshteinDistance('statuus', 'status') 的执行结果就是 `1` ,如下:
``` javascript
levenshteinDistance('statuus', 'status')
// => 1
而把 saturday
改为 sunday
最少需要改动三次(r 改为 n,删掉 t, 删掉 a),那么 levenshteinDistance('saturday', 'sunday') 的执行结果就是 3
,如下:
levenshteinDistance('saturday', 'sunday')
// => 3
这个算法使用了动态规划的**来设计。《算法导论》将解动态规划问题的方法总结出了两个思路,自底向上法和带缓存的递归法。这个问题使用自底向上法求解。
拿从 saturday
到 sunday
这两个字符串举例。首先,画出一张表,这是自底向上法的第一步。
- | - | s | a | t | u | r | d | a | y |
- | (0,0) | (5,0) | |||||||
s | (1,1) | ||||||||
u | |||||||||
n | |||||||||
d | (2,4) | (8,4) | |||||||
a | (0,5) | ||||||||
y | (8,6) |
这个表中的单元格中的值,代表相应字符串的编辑距离,比如表格中标示的:
saturday
到 sunday
的编辑距离。s
到 s
的编辑距离。satur
到空字符串的编辑距离。saturday
到 sund
的编辑距离。sa
到 sund
的编辑距离。sunda
的编辑距离。第一行表示某个字符串到空字符串的编辑距离,而第一列表示空字符串到某个字符串的编辑距离。任何字符串到空字符串的编辑距离都等于自身的长度,同样的空字符串到任何目标字符串的编辑距离都等于目标字符串的长度。所以一开始,表格第一行和第一列的值就是已知的了,填上第一行和第一列的值后得到的表格如下。
- | - | s | a | t | u | r | d | a | y |
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s | 1 | (1,1) | (1,2) | (1,2) | |||||
u | 2 | (2,1) | (2,2) | (2,3) | |||||
n | 3 | ||||||||
d | 4 | ||||||||
a | 5 | leftOver | over | ||||||
y | 6 | left | target |
target
所在的单元格的值,就是从 saturday
到 sunday
的编辑距离,也就是我们要找的最终答案。接下来,说说为什么求解编辑距离的方法要叫做自底向上法,根据 Levenshtein distance 的数学定义(看不懂可以无视):
可以看到,想要求 target 的值,就得从 left + 1
,over + 1
和 leftOver + match (a[i],b[j])
中找最小的值。 而 match 函数有如下定义。
// 如果两个参数相等,则返回 0,否则返回 1
var match = function (str1, str2) {
return str1 === str2 ? 0 : 1
}
而在这里
a = saturday
,b = sunday
, 而target
是最后一个单元格,所以a[i] = y
,b[j] = y
分别为两个字符串的最后一个字符。
无论如何,想要知道 target 的值,就得先知道它左边,左上边和上边也就是 left
,leftOver
,over
这几个单元格的值。很显然,一开始我们并不知道 left
,leftOver
,over
这几个单元格的值。但好在第一行和第一列的值是已知的,所以我们可以 “自底向上” 的逐个从 (1,1) , (1,2), (1,3) ...的值求起,当 x 为 1 的行填满后,再开始求 (2,1) , (2,2), (2,3) ...... ,就这么一直推导下去,直到整个表格被填满,答案自然也就水落石出了。
现在知道为什么这种方法要叫自底向上法了么。
填满后的表格如下:
- | - | s | a | t | u | r | d | a | y |
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
u | 2 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 |
n | 3 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 6 |
d | 4 | 3 | 3 | 3 | 3 | 4 | 3 | 4 | 5 |
a | 5 | 4 | 3 | 4 | 4 | 4 | 4 | 3 | 4 |
y | 6 | 5 | 4 | 4 | 5 | 5 | 5 | 4 | 3 |
我认为是时候贴代码了
// 如果两个参数相等,则返回 0,否则返回 1
var match = function (str1, str2) {
return str1 === str2 ? 0 : 1
}
// 求 list1 和 list2 的编辑距离
// levenshteinDistance('saturday', 'sunday', match)
// => 3
var levenshteinDistance = function (list1, list2, match) {
var len1 = list1.length,
len2 = list2.length,
matrix = [], // 表格
left,
over,
leftOver,
i,
j
// 填写表格的第一行和第一列
for (i = 0; i <= len1; i++) {
matrix[i] = []
matrix[i][0] = i
}
for (i = 0; i <= len2; i++) {
matrix[0][i] = i
}
// 自底向上推导
for (i = 1; i <= len1; i++) {
for (j = 1; j <= len2; j++) {
over = matrix[i][j - 1]
left = matrix[i - 1][j]
leftOver = matrix[i - 1][j - 1]
matrix[i][j] = Math.min(
left + 1,
over + 1,
leftOver + match(list1[i - 1], list2[j - 1])
)
}
}
// 将最后一个单元格的值返回
return matrix[len1][len2]
}
现在可以知道 Git 是将当前的指令跟指令库里边的指令做求编辑距离,然后将编辑距离小到一定程度的指令提供给我们备选。其实 Levenshtein distance 算法不仅可以弄明白 Git 为何会知道相近的选项,它还能做更多,比如求解出从一个字符串变化到另外一个字符串的最小步骤,甚至这个世界上许许多多 diff 算法都包含有它的影子。试想一下,有一天碰到了一个需求,要求比对前后两个版本的文章被作出了哪些改动,要如何解决。我在 2014 年做一个试题编辑系统的时候,就有碰到这样的需求,当时在网上查了好久好久,最后是通过回溯 Levenshtein distance 返回的整个的表格解决的。有时间我会再写一篇文章,回忆一下如何通过回溯 Levenshtein distance 返回的表格求出从一个字符串到另外一个字符串的最小步骤。
用不同的算法**解决同样一个问题,可以了解各种算法**之间的异同,加深对它们的理解。之前分享了一篇用贪心法求解 0-1 背包问题的文章,贪心法很快也很简单,但是它并不能总是得到最优解。而动态规划则不同,它不快,但总是能得到最优解。为了让问题描述更加生动以及容易理解,我把背包问题换了种说法,成了 老板请吃饭问题
,那么这次依然使用这个问题来包装 0-1 背包问题。
很久很久以前,有一个如你我般忠厚善良的可爱码农,在连续加班大半年以后,老板终于看到了他人性的光辉,决定请他吃晚餐。下班后,他们来到一个餐馆,餐馆的服务员给了他们如下一份菜单,老板让码农随意点菜,但不要重复点。而他们只能吃下 30 两重的东西,多吃一两都会胃炸裂而亡。那么问题来了,这位可爱的码农在不吃死的情况下,最多能花掉老板多少钱,如何点菜可以到达这个数目呢?
// 以下是他们所能吃的东西的上限和菜单
var capacity = 30,
collections = [
{name: '米饭' , weight: 7, price: 10},
{name: '宫保鸡丁' , weight: 6, price: 40},
{name: '紫菜蛋花汤' , weight: 12, price: 30},
{name: '水煮牛肉' , weight: 10, price: 50},
{name: '海鲜蒸蛋' , weight: 8, price: 35},
{name: '炭烤生蚝' , weight: 2, price: 40},
{name: '白灼时蔬' , weight: 5, price: 30}
]
世界上那么多种算法,但能引起诸广泛共鸣和讨论的往往是动态规划,可见它有多么迷人。当我们在算法书上碰到这种算法时,书上往往会说,动态规划适合用来解决有着 重叠子问题
和 最优子结构
性质的问题,解决问题的关键在于 如何定义子问题
而定义子问题的关键又是定义 问题的状态
和 状态转移方程
。看到这里,懂得动态规划的人一眼就知道说的是什么,而不懂的人看到这些术语往往就懵逼了。那么这是先有鸡,还是先有蛋呢?
总之,这里不是算法书,所以我们的码农还是打算先老老实实填表再说。
动态规划在许多时候一言不合就要填表,既然要填表,首先就是要把表建立出来。而表是基于要解决的问题所建立的,要解决的问题是:
解决问题要一个一个来,观察第一个问题,会发觉有两个参数 菜单
和 饭量上限
。那么可以用它来作为表的纵坐标和横坐标。这样就得到下列二维表(可以左右拖动):
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
0 空 | (0,0) | ||||||||||||||||||||||||||||||
1 米饭 | |||||||||||||||||||||||||||||||
2 宫保鸡丁 | |||||||||||||||||||||||||||||||
3紫菜蛋花汤 | (10,3) | ||||||||||||||||||||||||||||||
4 水煮牛肉 | |||||||||||||||||||||||||||||||
5 海鲜蒸蛋 | (25, 5) | ||||||||||||||||||||||||||||||
6 炭烤生蚝 | |||||||||||||||||||||||||||||||
7 白灼时蔬 | (9,7) | (30,7) |
表格里只把菜名标了出来,实际上每道菜除了菜名之外,还有份量和价格两个属性。
这个表格里每个单元格的值,都是在当前饭量上限的限制下,从当前菜单所能点出的最高总价,如:
用膝盖想也知道,当菜单是空以及当饭量上限为 0 的时候,是不可能点出哪怕一毛钱的菜的。所以表格的第一行第一列的值都为 0 。
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
0 空 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 米饭 | 0 | ||||||||||||||||||||||||||||||
2 宫保鸡丁 | 0 | ||||||||||||||||||||||||||||||
3紫菜蛋花汤 | 0 | ||||||||||||||||||||||||||||||
4 水煮牛肉 | 0 | ||||||||||||||||||||||||||||||
5 海鲜蒸蛋 | 0 | ||||||||||||||||||||||||||||||
6 炭烤生蚝 | 0 | ||||||||||||||||||||||||||||||
7 白灼时蔬 | 0 | (30,7) |
接下来要考虑的就是根据表格里边现有的值,推算出整个表格所有单元格的值了,从竖方向填写整个表格(其实横方向也可以)。因为每个单元格的值,都是在当前饭量上限的限制下,从当前菜单所能点出的最高总价,码农每往下走一个单元格,都会碰到一道新的菜,所以他每一次都应该问自己如下问题:
当饭量上限为 x 的时候,为了获取最高总价, y 这道菜点还是不点:
x - 当前物品重量
说明肚子还有刚好可以装这下道菜的空间。好现在举例说明,为了说明方便,手动填写部分表格。
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
0 空 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 米饭 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | |||||||||||||||||||||||
2 宫保鸡丁 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | (7, 2) | |||||||||||||||||||||||
3紫菜蛋花汤 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | ||||||||||||||||||||||||
4 水煮牛肉 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | ||||||||||||||||||||||||
5 海鲜蒸蛋 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | ||||||||||||||||||||||||
6 炭烤生蚝 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | ||||||||||||||||||||||||
7 白灼时蔬 | 0 | 0 | 40 | 40 | 40 | 30 | 40 |
// 菜单
var collections = [
{name: '米饭' , weight: 7, price: 10},
{name: '宫保鸡丁' , weight: 6, price: 40},
{name: '紫菜蛋花汤' , weight: 12, price: 30},
{name: '水煮牛肉' , weight: 10, price: 50},
{name: '海鲜蒸蛋' , weight: 8, price: 35},
{name: '炭烤生蚝' , weight: 2, price: 40},
{name: '白灼时蔬' , weight: 5, price: 30}
]
观察上面的表格,可得到:
这里 (7, 2) 单元格多了一个可选项‘宫保鸡丁’,毫无疑问,这是要点的。因为 7 的饭量上限,只能从‘米饭’和‘宫保鸡丁’中选一份,但‘宫保鸡丁’的总价比‘米饭’高。
那是怎么得出点宫保鸡丁这个结果的呢,如下:
如此一来,程序的流程就出来了,如下:
var capacity = 30,
collections = [
{name: '米饭' , weight: 7, price: 10},
{name: '宫保鸡丁' , weight: 6, price: 40},
{name: '紫菜蛋花汤' , weight: 12, price: 30},
{name: '水煮牛肉' , weight: 10, price: 50},
{name: '海鲜蒸蛋' , weight: 8, price: 35},
{name: '炭烤生蚝' , weight: 2, price: 40},
{name: '白灼时蔬' , weight: 5, price: 30}
]
// 动态规划
var getMatrix = function (collections, capacity) {
var len = collections.length,
matrix = [],
currentPrice = 0,
x,
y
// 建立二维表格,并且将第一行和第一列的值初始化为 0
for (x = 0; x <= capacity; x++) {
matrix[x] = []
matrix[x][0] = 0
}
for (y = 0; y <= len; y++) {
matrix[0][y] = 0
}
// 从上到下,从左往右遍历表格
for (x = 1; x <= capacity; x++) {
for (y = 1; y <= len; y++) {
// 如果当前菜的重量超过当前饭量上限则判定为不点
if (collections[y - 1].weight > x) {
matrix[x][y] = matrix[x][y - 1]
} else {
// 从点和不点中找到最大值
matrix[x][y] = Math.max(
matrix[x - collections[y - 1].weight][y-1] + collections[y - 1].price, // 点当前菜
matrix[x][y - 1] // 不点当前菜
)
}
}
}
return matrix
}
console.log(getMatrix(collections, capacity))
这是填写完整的表
- | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
0 空 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 米饭 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
2 宫保鸡丁 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 | 50 |
3紫菜蛋花汤 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 50 | 50 | 50 | 50 | 50 | 70 | 70 | 70 | 70 | 70 | 70 | 70 | 80 | 80 | 80 | 80 | 80 | 80 |
4 水煮牛肉 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 50 | 50 | 50 | 50 | 50 | 50 | 90 | 90 | 90 | 90 | 90 | 90 | 90 | 100 | 100 | 100 | 100 | 100 | 120 | 120 | 120 |
5 海鲜蒸蛋 | 0 | 0 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 50 | 50 | 50 | 50 | 75 | 75 | 90 | 90 | 90 | 90 | 90 | 90 | 90 | 100 | 125 | 125 | 125 | 125 | 125 | 125 | 125 |
6 炭烤生蚝 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 40 | 80 | 80 | 80 | 80 | 90 | 90 | 90 | 90 | 115 | 115 | 130 | 130 | 130 | 130 | 130 | 130 | 130 | 140 | 165 | 165 | 165 | 165 | 165 |
7 白灼时蔬 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 70 | 80 | 80 | 80 | 80 | 90 | 110 | 110 | 110 | 115 | 120 | 130 | 130 | 130 | 145 | 145 | 160 | 160 | 160 | 165 | 165 | 165 | 165 | 170 |
整个填表的过程就是动态规划的过程。码农已经利用动态规划的**知道了他最多可以吃掉老板 170 块钱。现在来说说理论的东西,不喜欢直接跳过:
转至维基百科
表已经填好,接下来就是回溯这个表格从中找出点哪几道菜可以吃掉老板 170 块钱。
回溯的思路非常简单:
// collections 菜单, capacity 饭量上限
var knapsackProblemByDynamicProgramming = function (collections, capacity) {
var matrix = getMatrix(collections, capacity), // 获得填写好的表格, getMatrix 是之前的动态规划算法
len = collections.length,
result = {
totalPrice: 0,
totalWeight: 0,
selected: []
},
x,
y
// 将 x, y 设置为最后一个单元格的 x, y
x = capacity
y = len
// 开始回溯
while (x > 0 || y > 0) {
// 如果当前菜的重量超过当前饭量则判定为不点
if (collections[y - 1].weight > x) {
y--
} else {
// 判断当前单元格的值是点下当前菜得来的还是不点得来的
if ((matrix[x - collections[y - 1].weight][y-1] + collections[y - 1].price) > matrix[x][y - 1]) {
// 是点下得来的
result.selected.unshift(collections[y - 1]) // 将当前菜加入结果
x = x - collections[y - 1].weight // 移动 x
y-- // 移动 y
} else {
// 是不点得来的
y-- // 移动 y
}
}
}
// 计算结果集合中价格和重量的总和
result.selected.forEach(function (item) {
result.totalPrice += item.price
result.totalWeight += item.weight
})
return result
}
从篇幅上看也知道,动态规划的复杂性比贪心法高出了不少,有时候甚至会填写三维表,四维表甚至是更高维度的表。但它总是能得到最优结果,可能也因为如此,它才如此迷人。
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.