javascript求解0-1背包问题

连喊了四声，终于从噩梦中醒来，看了看时间：3点06分。我不知道是否是自己最近做错了事情良心的谴责，还是因为想家了？左思右想，渐渐从梦里那恐惧的气氛中缓解出来，意识也变得非常清醒，想起昨晚给自己留下了一个0-1背包问题，简单在脑海里回顾了一下，在有问题的地方加了一个条件判断，早晨起床后，便把这个问题整理了一下。

愿一切都未曾发生，就如梦一般，回到现实之后，我还可以这样平稳的看着自己，拥有自己。

“0-1背包”问题是一个简单的动态规划问题，因为只有0或者1两种情况，相对其他的最优策略问题要简单的多，不过也只是一个时间复杂度的问题。比如在角色扮演类游戏中，游戏人物身上经常会携带一个背包，背包中可以放置武器装备、药水道具等等，但是背包的容量有限，我们需要思考如何携带合适的物品组合，可以使我们的收益获得最大。对于单个物品来说，我们可以放，也可以不放，如果放入背包记为1，不放入记为0。因此这个问题也通称为“0-1背包”问题。

假设现在有n个物品，每个物品的收益为vi，重量为wi，背包容量为W。我们需要对全部的组合情况进行比对，直到我们找到收益最大的那种组合。
我们用一维数组w[n]记录每个物品的重量，v[n]记录每个物品的收益，x[n]记录每个物品装入情况，装入记为1，不装入记为0。那么问题的约束可以表示为：

w1×x1 + w2×x2 + w3×x3 + … + wn×xn ≤ W

我们需要求解一个x[n]，使得：

v1×x1 + v2×x2 + v3×x3 + … + vn×xn

的值最大。

经过整理后，我们的问题表示就变得比较规范和可计算，接下来就要研究如何计算这个问题。

我们可以从第一个物品开始向后遍历计算，我们使用数组x[n]记录当前的最优遍历情况，使用数组xt[n]来记录当前的遍历情况。

• 首先，判断是否已经遍历完毕，如果是的话就说明当前已经完成了一次全部物品的遍历，判断当前的收益是否比当前最优收益大，如果是，将当前的遍历情况数组xt[n]保存到当前最后遍历情况数组x[n]中，退出当前遍历；否则，直接退出遍历。

• 然后，如果没有遍历完毕，那么计算当前物品加入后是否会超出背包容量W，如果没有超出，则将当前物品加入，继续向后遍历下一个物品。

• 如果超出，继续向后遍历下一个物品。

• 一次遍历完成后，开始进行回退，即返回到前一个遍历状态，这时候就需要将当前物品从背包中取出来，然后继续向后遍历下一个物品。

我们可以用下面的图示来描述整个遍历过程。

其实现代码如下：

/**
 * 背包对象
 * W: 背包最大容量
 *
 */
function Backpack ( W ) {
  // 背包的容量
  this.W = W
  // 当前加入背包中的物品总重量
  this.cW = 0
  // 当前加入背包中物品的总收益
  this.cV = 0
  // 当前的最优解数组
  this.X = []
  // 当前的最优收益
  this.V = 0
  // 当前物品重量数组
  this.wArray = []
  // 当前物品收益数组
  this.vArray = []
  // 待选取的物品数量
  this.n = 0

}

/**
 * 遍历物品
 * 
 * index: 当前序号
 * xt: 当前的遍历情况
 */
Backpack.prototype.traverseGoods = function ( index, xt ) {

  // 如果已经遍历到最后
  if(index >= this.n) {
    if (this.V < this.cV) {
      for (var i = 0; i < this.n; i++) {
        this.X[i] = xt[i]
      }
      this.V = this.cV
    }
    return
  }

  // 当前物品加入后未超出背包容量时
  // 需要将当前物品加入背包后继续向后遍历
  if (this.cW + this.wArray[index] <= this.W) {
    // 将当前物品加入背包
    xt[index] = 1
    this.cW += this.wArray[index]
    this.cV += this.vArray[index]
    // 向后继续遍历
    this.traverseGoods( index+1, xt )
    this.cW -= this.wArray[index]
    this.cV -= this.vArray[index]
  }
  // 回溯时将当前物品不加入背包遍历后续物品
  xt[index] = 0
  this.traverseGoods( index+1, xt )

}

/**
 * 计算最优组合
 * 
 * goodArr: 物品序列
 *
 */
Backpack.prototype.getBestFormGoodArray = function (goodArr) {
  // 物品序列长度
  this.n = goodArr[0].length
  if (this.n <= 0) return
    
  this.wArray = goodArr[0]
  this.vArray = goodArr[1]

  var xt = []

  this.traverseGoods( 0, xt )

  return {
    X: this.X,
    V: this.V
  }
}

var backpack = new Backpack(10)
var goodArr = [
                [2,5,4,2],
                [6,3,5,4]
              ]
backpack.getBestFormGoodArray(goodArr)