01背包的原理其实很简单,其实就是从不放背包的情况下一层层去比较放入这个物品后的背包价值和不放入物品的价值的比较谁大。即其公式主要为

01背包未优化情况​

我理解能力比较弱,所以从一个实际例子来出发吧

举例:

​ 5个物品,其(w,v)分别为 (2,3)、(4、5)、(3,7),那么从1物品到3物品逐层向上的填表结果如下图所示:

🎒 0 1 2 3 4 5 6
3物品 0 0 0 7 7 10 10
2物品 0 0 3 3 5 5 8
1物品 0 0 3 3 3 3 3

​ 原始的代码就显示非常蠢了:

1
2
3
4
5
6
7
8
9
for i := 0; i < n; i++ {
for j := 0; j < w; j++ {
if(j < w[i]) {
m[i][j] = m[i - 1][j]
} else {
m[i][j] = math.Max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
}
}
}

​ 上面这个奇丑无比的代码其实空间复杂度是n²,非常的爆炸,所以下面可以优化他的空间到n

01背包优化空间

​ 根据上面的推导式我们可以得出,每一次的m[i]层只和m[i - 1]层有联系,所以我们可以将二维数组直接化为一维数组,即滚动数组。

1
2
3
4
5
for i := 0; i < n; i++ {
for j := w; j >= w[i]; j-- {
m[j] = math.Max(m[j], m[j - w[i]] + v[i])
}
}

​ 这里有一个注意点就是上面未优化的代码的j是从0开始递增遍历,而这里的代码是从w开始递减,这个是因为我们只有一个一维数组,每一次的遍历是要和上一次的结果进行比较的,如果我们从前往后遍历,那么最开始的那部分就会被覆盖,那么本次遍历到后面的时候发现前面的那部分都已经被覆盖掉了,代码就会崩掉了。