算法 最长递增子序列 与 0 1 背包问题

最长递增子序列

在计算机科学中,最长递增子序列(longest increasing subsequence)问题是指,在一个给定的数值序列中,找到一个子序列,使得这个子序列元素的数值依次递增,并且这个子序列的长度尽可能地大。

同样是一个经典的动态规划算法,与最长公共子序列相比,更加简单一些。

function lis(n) {
let len = n.length
let array = new Array(len).fill(1)

for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
if (n[i] > n[j]) {
array[i] = Math.max(array[i], array[j] + 1)
}
}
}
return Math.max.apply(Math, array)
}

console.log(lis([0, 3, 4, 17, 2, 8, 6, 10, 11]))

值得一提的是LIS对于空间的占用是O(n)的,时间复杂度仍为O(n^2)

0-1背包问题

该问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。每个问题只能放入至多一次。

相比较于分数背包,01背包只能通过动态规划去解。

理解01背包解法的关键在于理解其最优子结构

假设我们拥有如下商品






















物品 ID / 重量价值
13
27
312

画一个表格来帮助我们理解整个流程










































物品 ID / 剩余容量012345
1033333
2037101010
3037121519

事实上,解法就是按照这个表格进行一步步的填写内容,一个表格内部的项将会依赖其他已经填好的项目内容。

首先,我们需要明确的是 所谓01背包,其实就是一个物品,只有两种情况,拿 与 不拿!

  • 首先,先填写我们目前只考虑拥有商品[0] 也就是整个表格的第一行,在拥有剩余空间i时的最大的价值
  • 随后开始填写第二行,我们首先设置其初始值为 上一行的同列的内部值 这代表了在增加一个选择的情况下,相同金额,我们大不了不拿这个商品,这里就是针对不拿
  • 接下来开始尝试增大这个价值,我们开始尝试回溯,也就是在上一行不拿当前物品的总量的情况下的价值,加上当前物品的价值(比较饶,确实很难解释,搭配代码看就很简单了),去寻找一个相对于不拿的更高值。这里就是针对于拿,并且我要看拿了是不是能增加我当前的价值。
function knapsack(w, v, C) {
let len = w.length

let table = new Array(len).fill(new Array(C + 1).fill(0))

for (let j = 0; j <= C; j++) {
table[0][j] = j >= w[0] ? v[0] : 0
}

for (let i = 1; i < len; i++) {
let cw = w[i]
for (let j = 0; j <= C; j++) {
table[i][j] = table[i - 1][j]
if (j >= cw) {
table[i][j] = Math.max(table[i][j], v[i] + table[i - 1][j - cw])
}
}
}
return table[len - 1][C]
}