回溯算法解决背包问题

1.描述：
石头收藏家小明在徒步登山的时候发现了一堆美丽的石头。这些石头价值不菲，但是都很重，小明自身的力气有限，一次只能拿他拿得动的一部分。每块石头的重量不同，价值也不同。问小明在力所能及的情况下能拿走价值多少的石头。
2.说明：小明只能搬运一次。
例如：小明只能拿得动 10 kg，每块石头的重量分别为2kg，3kg，5kg，7kg，对应的价值分别为 1万，5万，2万，4万。小明能拿的是 3kg 以及 7kg 的石头，价值 9 万。
3.输入：
使用分号(;)分隔三组数据。
第一组为一个整数，表示小明一次能搬运的最大重量。
第二组为一个使用逗号(,)分隔的数组，表示每块石头的重量。
第三组为一个使用逗号(,)分隔的数组，表示每块石头的对应的价值。
4.输出： 一个整数，表示小明这次能带回去的石头的总价。
5.输入样例： 10;2,3,5,7;1,5,2,4
6.输出样例： 9

这是一个经典的背包问题，背包问题(Knapsack problem)是一种组合优化的 NP 完全问题，其特点是时间复杂度很难优化，解法几乎都是在穷举法的基础上进行的。所以常见的解法可以是递归式的。
而本文介绍的回溯算法，也是穷举法的一种，只不过它可以根据适当的条件进行剪枝，从而达到优化的目的。

算法如下：

function solution(line) {
  let [sum, wlist, vlist] = line.split(";");
  sum = +sum; // 总承重
  wlist = wlist.split(","); // 重量数组
  vlist = vlist.split(","); // 价值数组

  let list = [];
  // 将重量与价值用对象的方式放在同一个数组中
  wlist.forEach((item,index) => {
    list.push({
      w: +item,
      v: +vlist[index],
    });
  });
  // 按照重量·价值比进行排序，单位重量价值高的排在前面
  list.sort((a,b)=>a.w/a.v-b.w/b.v);

  let L = wlist.length,
      W = 0, // 拿取的重量
      max = 0, // 拿取的总价值
      _max = 0, // 缓存最大总价值
      vSum = vlist.reduce((sum,item) => sum + item,0); // 剩余石头的总价值

  function backtrack(n) {
    if(n === L) { // 若石头已拿到最后一个
      if(max > _max) { // 若最大总价值破纪录，则更新最大总价值
        _max = max;
      }
      return;
    }
    if(W + list[n].w <= sum) { // 若剩余承重允许拿取此石头
      W += list[n].w; // 计算已拿取的重量
      max += list[n].v; // 更新已拿取的总价值
      vSum -= list[n].v; // 计算剩余总价值
      backtrack(n+1); // 继续拿取下一个
      W -= list[n].w; // 回溯，放回此石头的重量
      max -= list[n].v; // 回溯，去掉此石头的价值
      vSum += list[n].v; // 回溯，剩余石头总价值中加回此石头的价值
    }
    if(max + vSum > _max) { // 若当前拿取的总价值加上剩余石头的总价值可以超过最大总价值，才继续拿取；否则剪枝
      backtrack(n+1);
    }
    return;
  }
  
  backtrack(0); // 从0开始
  return _max;
}