【数据结构与算法】三个经典案例带你了解动态规划

从表中我们可以看到，最大的公共子串长度为2，一共有两个长度为2的公共子串，分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符，即 ba 和 ac

根据上面的方法，我们来用代码封装一下求取最大公共子串的函数

function publicStr(s1, s2) {

// 创建一个表

let table = []

// 记录最大的公共子串长度

let max = 0

// 子串进行比较，将表填完整

for(let i = 0; i <= s1.length; i++) {

table[i] = []

for(let j = 0; j <= s2.length; j++) {

// 若行表头或列表头为0，格子里填0

if(i == 0 || j == 0) table[i][j] = 0;

// 若字符比对不相同

else if(s1[i – 1] !== s2[j – 1]) table[i][j] = 0;

// 字符比对相同

else {

// 当前格子的值等于左上角格子的值+1

table[i][j] = table[i – 1][j – 1] + 1

// 判断max是否为最大公共子串的长度

if(table[i][j] > max) max = table[i][j]

}

// 记录所有的最大公共子串的信息

let items = []

// 遍历整个表，找到所有子串长度为max的子串的最后一个字符的索引

for(let i = 0; i < s1.length; i ++) {

let current = table[i]

for(let j = 0; j < s2.length; j ++) {

if(current[j] === max) items.push(i)

}

console.log(最大子串长度为${max});

console.log(长度为${max}的子串有：);

for(let i in items) {

let start = items[i] – max

console.log(${s1.slice(start, start + max)});

}

我们用上述例子来验证一下该函数是否正确，同时我还打印了一下表的结果，大家可以跟实例中的比对一下是否正确

let s1 = ‘abaccd’

let s2 = ‘badacef’

publicStr(s1, s2)

/* 打印结果：

最大公共子串长度为2

长度为2的子串有：

表：[

[0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 1, 0, 1, 0, 0, 0],

[0, 1, 0, 0, 0, 0, 0, 0],

[0, 0, 2, 0, 1, 0, 0, 0],

[0, 0, 0, 0, 0, 2, 0, 0],

[0, 0, 0, 0, 0, 1, 0, 0],

[0, 0, 0, 1, 0, 0, 0, 0]

]

四、案例三：背包问题

===================================================================

背包问题也算是一个非常经典的问题，假设现在你的面前有4种珠宝，它们的重量分别为 3 、3 、4 、5 ，它们的价值分别为 4 、6 、7 、9，现在你有一个能装下重量为 8 的物品，请问你会如何挑选才能使利益最大化？

当然最简单的办法就是写出所有的组合，然后计算每种组合的价值，然后就能获得利益最大化的方案

这用递归实现是非常简单的，代码如下

// 封装一个判断大小的函数

function max(v1, v2) {

return v1 > v2 ? v1 : v2

}

// 主函数，用于判断当前背包容量下，存放某个物品的最大收益

// 参数：背包容量、存放每个物品重量的数组、存放每个物品价值的数组、物品标号

function knapsack(capacity, size, value, n) {

// 如果没有物品了或者背包没容量了，则最大收益为0

if(n == 0 || capacity == 0) return 0;

// 物品n的重量大于背包容量

else if(size[n – 1] > capacity) {

// 返回上一个物品的最大收益

return knapsack(capacity, size, value, n – 1)

}

// 物品n的重量小于背包容量

else {

// 此时有两种选择：第一种：拿该物品 ; 第二种：不拿该物品

// 我们要取其中收益最大的方案，因此用到max函数

return max(value[n – 1] + knapsack(capacity – size[n – 1], size, value, n – 1), knapsack(capacity, size, value, n – 1))

}

// 代码测试

let capacity = 8

let size = [3, 3, 4, 5]

let value = [4, 6, 7, 9]

let n = 4

let res = knapsack(capacity, size, value, n)

console.log(res) // 15 , 表示最大收益价值为15

正如我们文章开头所说的，这样的递归效率总归是不太高的，因此我们要将其用动态规划实现，并且我们将需求改变一下，不光要求出最大收益价值，还要知道是拿了哪几样物品。

同样的，我们先创建一个表，用来记录每一种物品在任一背包容量下的最大收益

很明显，当背包容量为0时，我们能获得的最大收益一定为0；表中物品编号为0的这一行全部都要填上0，因为这是我们添加的对照行，并没有编号为0的物品，因此结果如图所示：

现在我们从编号为1的物品开始，判断其在背包容量为 1 ~ 8 的情况下，我们能获取到的最大利益为多少。显而易见，物品1的重量为3，因此当背包容量小于3时，最大收益都为0；当背包容量大于等于3时，因为还没有考虑别的物品，因此我们能获取的最大收益就等于物品1的价值，即等于4，结果如图所示：

接着我们考虑编号为2的物品在背包容量为 1 ~ 8 的情况下，我们能获取到的最大利益为多少。

首先知道物品2的重量为3，因此在背包容量小于3时，我们无法放入物品2，那么此时的最大收益就等于在当前背包容量下，放入物品1的最大收益；

当背包容量大于等于3时，我们能放入物品2，因此我们现在有两种选择：第一种就是不放物品2，那么我们就只能放物品1，所以我们能获得的最大收益就等于在此背包容量下放入物品1的最大收益；第二种就是放物品2，因为我们已经放了物品2了，只剩一个物品1了，所以此时的最大收益就等于物品2的价值 + 背包剩余容量下放入物品1的最大收益。我们要取这两种情况中收益最大的方案

填表过程如下图所示：

接着我们又考虑编号为3的物品在背包容量为 1 ~ 8 的情况下，我们能获取到的最大利益为多少。

首先知道物品3的重量为4，因此在背包容量小于4时，我们无法放入物品3，那么我们还需要考虑的就有物品1和物品2，从上一步骤得知，物品2的最大收益时在考虑了物品1的基础上得出的，因此我们只需要考虑放入物品2的最大收益即可，那么此时的最大收益就等于在当前背包容量下，放入物品2的最大收益；

当背包容量大于等于4时，我们能放入物品4，与上一个步骤类似，我们有两种选择，即放物品3和不放物品3

填表结果如下图所示：

同理，最后一行的填表过程如下图所示：

最终的填表结果如下图所示：

在表中可以很明显地看到，我们在背包容量为8的情况下，能获取到的最大收益为15

此时，我们还需要倒着推回去，判断一下是拿了哪几样物品才获取到的最大收益

首先找到最大收益对应的格子为物品4，然后我们判断一下该收益是否等于前一种物品（物品3）的最大收益，若等于，则表示没有放入物品4；否则表示放入了物品4。

为什么会这样判断呢？因为我们说过，在判断一个物品在某背包容量下的最大收益时，当物品重量大于背包容量或者我们选择不放入该物品时，此时的最大收益就等于前一种物品在此背包容量下的最大收益

所以这里能判断，我们放入了物品4，则此时背包容量只剩 8 - 5 = 3，所以我们找到物品3在背包容量等于3情况下最大收益对应的格子，同样判断一下上一种物品（物品2）的最大收益是否等于此格子中的最大收益，当前判断为相等，因此我们没有放入物品3

当前背包容量仍为3，我们找到物品2在背包容量等于3情况下最大收益对应的格子，判断当前最大收益不等于上一种物品（物品1）在背包容量为3情况下的最大收益，因此我们放入了物品2

则此时背包容量为 3 - 3 = 0了，无法再放入任何物品了，所以我们就可以得出结论，我们在放入物品2和物品4的情况下收益最大，最大收益价值为15

上面讲解了背包问题的动态规划思路，下面我们用代码来实现一下

function knapsack(capacity, size, value, n) {

// 返回较大的值

function max(v1, v2) {

return v1 > v2 ? v1 : v2

}

let table = []

// 生成长度为n的表

for(let i = 0; i <= n; i++) {

table[i] = []

}

// 判断每种物品面对不同背包容量时的最大收益

for(let i = 0; i <= n; i++) {

for(let j = 0; j <= capacity; j++) {

// 物品种类序列为0或者背包容量为0时，最大收益为0

if(i == 0 || j == 0) table[i][j] = 0;

// 背包容量小于物品重量时，最大收益等于上一种物品在此背包容量下的最大收益

else if(size[i – 1] > j) {

table[i][j] = table[i – 1][j]

}

/* 背包容量大于物品重量时，最大收益分两种情况：

第一种情况：不放此物品。则最大收益等于上一种物品在此背包容量下的最大收益；

第二种情况：放此物品。则最大收益等于该物品的收益加上剩余背包容量下，上一种物品的最大收益

else {

table[i][j] = max(table[i – 1][j], value[i – 1] + table[i – 1][j – size[i – 1]])

}

// 最大收益值

let max_value = 0

let which = -1

// 寻找在背包容量为capacity时的最大收益值，以及最大收益值所对应的物品种类

for(let i in table) {

let k = table[i][capacity]

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
因此收集整理了一份《2024年Web前端开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。