正文
![]()
![]()
钟钦成
钟钦成，网名为司徒正美，国内著名的前端专家，对浏览器兼容性问题/选择器引擎/react内部机制等具有深厚的积累，开发有avalon/anu等前端框架，著有《JavaScript框架设计》一书。
1.4 选择物品
上篇讲解了如何求得最大价值，现在我们看到底选择了哪些物品，这个在现实中更有意义。许多书与博客很少提到这一点，就算给出的代码也不对，估计是在设计状态矩阵就出错了。
仔细观察矩阵，从 ${f(n-1,W)}$ 逆着走向 ${f(0,0)}$ ，设 i=n-1 , j=W ，如果 ${f(i,j)}$==${f(i-1,j-wi)+vi}$ 说明包里面有第i件物品，因此我们只要当前行不等于上一行的总价值，就能挑出第i件物品，然后j减去该物品的重量，一直找到 j = 0 就行了。
function knapsack(weights, values, W){
var n = weights.length;
var f = new Array(n)
f[-1] = new Array(W+1).fill(0)
var selected = [];
for(var i = 0 ; i < n ; i++){ //注意边界，没有等号
f[i] = [] //创建当前的二维数组
for(var j=0; j<=W; j++){ //注意边界，有等号
if( j < weights[i] ){ //注意边界， 没有等号
f[i][j] = f[i-1][j]//case 1
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2
}
}
}
var j = W, w = 0
for(var i=n-1; i>=0; i--){
if(f[i][j] > f[i-1][j]){
selected.push(i)
console.log("物品",i,"其重量为", weights[i],"其价格为", values[i])
j = j - weights[i];
w += weights[i]
}
}
console.log("背包最大承重为",W," 现在重量为", w, " 总价值为", f[n-1][W])
return [f[n-1][W], selected.reverse() ]
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)
1.4.1 使用滚动数组压缩空间
所谓滚动数组，目的在于优化空间，因为目前我们是使用一个 ${ij}$ 的二维数组来储存每一步的最优解。在求解的过程中，我们可以发现，当前状态只与前一行的状态有关，那么更之前存储的状态信息已经无用了，可以舍弃的，我们只需要存储当前状态和前一行状态，所以只需使用 ${2j}$ 的空间，循环滚动使用，就可以达到跟 ${i*j}$ 一样的效果。这是一个非常大的空间优化。
function knapsack(weights, values, W){
var n = weights.length
var lineA = new Array(W+1).fill(0)
var lineB = [], lastLine = 0, currLine
var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行
for(var i = 0; i < n; i++){
currLine = lastLine === 0 ? 1 : 0 //决定当前要覆写滚动数组的哪一行
for(var j=0; j<=W; j++){
f[currLine][j] = f[lastLine][j] //case2 等于另一行的同一列的值
if( j>= weights[i] ){
var a = f[lastLine][j]
var b = f[lastLine][j-weights[i]] + values[i]
f[currLine][j] = Math.max(a, b);//case3
}
}
lastLine = currLine//交换行
}
return f[currLine][W];
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)
我们还可以用更 hack 的方法代替 currLine, lastLine 。
function knapsack(weights, values, W){
var n = weights.length
var f = [new Array(W+1).fill(0),[]], now = 1, last //case1 在这里使用es6语法预填第一行
for(var i = 0; i < n; i++){
for(var j=0; j<=W; j++){
f[now][j] = f[1-now][j] //case2 等于另一行的同一列的值
if( j>= weights[i] ){
var a = f[1-now][j]
var b = f[1-now][j-weights[i]] + values[i]
f[now][j] = Math.max(a, b);//case3
}
}
last = f[now]
now = 1-now // 1 - 0 => 1;1 - 1=> 0; 1 - 0= > 1 ....
}
return last[W];
}
注意，这种解法由于丢弃了之前 N 行的数据，因此很难解出挑选的物品，只能求最大价值。
1.4.2使用一维数组压缩空间
观察我们的状态迁移方程:
![]()
weights 为每个物品的重量， values 为每个物品的价值， W 是背包的容量， i 表示要放进第几个物品， j 是背包现时的容量（假设我们的背包是魔术般的可放大，从 0 变到 W ）。
我们假令 i = 0
![]()
f中的-1就变成没有意义，因为没有第-1行，而 weights[0] , values[0] 继续有效， ${f(0,j)}$ 也有意义，因为我们全部放到一个一维数组中。于是:
![]()
这方程后面多加了一个限制条件，要求是从大到小循环。为什么呢？
假设有物体 ${\cal z}$ 容量2，价值 ${vz}$ 很大，背包容量为5，如果 j 的循环顺序不是逆序，那么外层循环跑到物体 ${\cal z}$ 时， 内循环在 ${j=2}$ 时 ， ${\cal z}$ 被放入背包。当 ${j=4}$ 时，寻求最大价值，物体 z 放入背包， ${f(4)=max(f(4),f(2)+vz) }$ ，这里毫无疑问后者最大。但此时 ${f(2)+v_z}$ 中的 ${f(2)}$ 已经装入了一次 ${\cal z}$ ，这样一来
${\cal z}$ 被装入两次不符合要求， 如果逆序循环 j ， 这一问题便解决了。
javascript 实现：
function knapsack(weights, values, W){
var n = weights.length;
var f = new Array(W+1).fill(0)
for(var i = 0; i < n; i++) {
for(var j = W; j >= weights[i]; j--){
f[j] = Math.max(f[j], f[j-weights[i]] +values[i]);
}
console.log(f.concat()) //调试
}
return f[W];
}
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)
1.5 递归法解01背包
由于这不是动态规则的解法，大家多观察方程就理解了：
function knapsack(n, W, weights, values, selected) {
if (n == 0 || W == 0) {
//当物品数量为0，或者背包容量为0时，最优解为0
return 0;
} else {
//从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
for (var i = n - 1; i >= 0; i--) {
//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品
//在这种情况的最优解为f(n-1,C)
if (weights[i] > W) {
return knapsack(n - 1, W, weights, values, selected);
} else {
var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
//返回选择物品i和不选择物品i中最优解大的一个
if (a > b) {
selected[i] = 0; //这种情况下表示物品i未被选取
return a;
} else {
selected[i] = 1; //物品i被选取
return b;
}
}
}
}
}
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
if(el){
console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
}
})
2. 完全背包问题
2.1 问题描述：
有 ${n}$ 件物品和 ${1}$ 个容量为W的背包。每种物品没有上限，第 ${i}$ 件物品的重量为 ${weights[i]}$ ，价值为 ${values[i]}$ ，求解将哪些物品装入背包可使价值总和最大。
2.2 问题分析：
最简单思路就是把完全背包拆分成01背包，就是把01背包中状态转移方程进行扩展，也就是说01背包只考虑放与不放进去两种情况，而完全背包要考虑 放0、放1、放2…的情况，
![]()
这个k当然不是无限的，它受背包的容量与单件物品的重量限制，即 ${j/weights[i]}$ 。假设我们只有1种商品，它的重量为20，背包的容量为60，那么它就应该放3个，在遍历时，就0、1、2、3地依次尝试。
程序需要求解 ${nW}$ 个状态，每一个状态需要的时间为 ${O（W/wi）}$ ，总的复杂度为 ${O(nWΣ(W/wi))}$ 。
我们再回顾01背包经典解法的核心代码
for(var i = 0 ; i < n ; i++){
for(var j=0; j<=W; j++){
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]))
}
}
}
现在多了一个 k ，就意味着多了一重循环
for(var i = 0 ; i < n ; i++){
for(var j=0; j<=W; j++){
for(var k = 0; k < j / weights[i]; k++){
f[i][j] = Math.max(f[i-1][j], f[i-1][j-k*weights[i]]+k*values[i]))
}
}
}
}
javascript的完整实现：
n completeKnapsack(weights, values, W){
var f = [], n = weights.length;
f[-1] = [] //初始化边界
for(var i = 0; i <= W; i++){
f[-1][i] = 0
}
for (var i = 0;i < n;i++){
f[i] = new Array(W+1)
for (var j = 0;j <= W;j++) {
f[i][j] = 0;
var bound = j / weights[i];
for (var k = 0;k <= bound;k++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - k * weights[i]] + k * values[i]);
}
}
}
return f[n-1][W];
}
//物品个数n = 3，背包容量为W = 5，则背包可以装下的最大价值为40.
var a = completeKnapsack([3,2,2],[5,10,20], 5)
console.log(a) //40
2.3 O(nW) 优化
我们再进行优化，改变一下f思路，让 ${f(i,j)}$ 表示出在前i种物品中选取若干件物品放入容量为 j 的背包所得的最大价值。
所以说，对于第 i 件物品有放或不放两种情况，而放的情况里又分为放1件、2件、…… ${j/w_i}$ 件。
如果不放, 那么 ${f(i,j)=f(i-1,j)}$ ；如果放，那么当前背包中应该出现至少一件第i种物品，所以 f(i,j) 中至少应该出现一件第 i 种物品,即 ${f(i,j)=f(i,j-wi)+vi}$ ，为什么会是 ${f(i,j-wi)+vi}$ ？
因为我们要把当前物品i放入包内，因为物品i可以无限使用，所以要用 ${f(i,j-wi)}$ ；如果我们用的是 ${f(i-1,j-wi)}$ ， ${f(i-1,j-wi)}$ 的意思是说，我们只有一件当前物品 i ，所以我们在放入物品i的时候需要考虑到第 i-1 个物品的价值 ${f(i-1,j-wi)}$ ；但是现在我们有无限件当前物品 i ，我们不用再考虑第 i-1 个物品了，我们所要考虑的是在当前容量下是否再装入一个物品 i ，而 ${(j-w_i)}$ 的意思是指要确保
${f(i,j)}$ 至少有一件第 i 件物品，所以要预留 c(i) 的空间来存放一件第 i 种物品。总而言之，如果放当前物品 i 的话，它的状态就是它自己”i”，而不是上一个”i-1”。
所以说状态转移方程为：
![]()
与01背包的相比，只是一点点不同，我们也不需要三重循环了
![]()
javascript 的完整实现：
function unboundedKnapsack(weights, values, W) {
var f = [],
n = weights.length;
f[-1] = []; //初始化边界
for (let i = 0; i <= W; i++) {
f[-1][i] = 0;
}
for (let i = 0; i < n; i++) {
f[i] = [];
for (let j = 0; j <= W; j++) {
if (j < weights[i]) {
f[i][j] = f[i - 1][j];
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - weights[i]] + values[i]);
}
}
console.log(f[i].concat());//调试
}
return f[n - 1][W];
}
var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);
我们可以继续优化此算法，可以用一维数组写
我们用 ${f(j)}$ 表示当前可用体积j的价值，我们可以得到和01背包一样的递推式：
![]()
-
function
unboundedKnapsack(
weights,
values,
W)
{
-
var n = weights
.length
,
-
f
= new
Array(
W +
1
).fill
(0
);
-
for(var i
=0; i
< n
;
++i
){
-
for(j =
weights[
i];
j <=
W;
++
j)
{
-
var tmp
= f[j
-weights
[i
]]+values
[i
];
-
f
[j]
= (f
[j
]
> tmp
)
? f
[j
]
: tmp
;
-
}
-
}
-
console
.log(f
)//调试
-
return f
[W];
-
}
-
var
a = unboundedKnapsack([3
, 2,
2
],
[5
,
10,
20
],
5);
//输出40
-
console
.log(a
);
