javascript背包问题详解

打算好好学一下算法，先拿背包问题入手。但是网上许多教程都是C++或java或python，大部分作者都是在校生，虽然算法很强，但是完全没有工程意识，全局变量满天飞，变量名不明所以。我查了许多资料，花了一个星期才搞懂，最开始的01背包耗时最多，以前只会枚举（就是普通的for循环，暴力地一步步遍历下去），递归与二分，而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。

篇幅可能有点长，但请耐心看一下，你会觉得物有所值的。本文以后还会扩展，因为我还没有想到完全背包与多重背包打印物品编号的方法。如果有高人知道，劳烦在评论区指教一下。

注意，由于社区不支持LaTex数学公式，你们看到${xxxx}$,就自己将它们过滤吧。

有${n}$件物品和${1}$个容量为W的背包。每种物品均只有一件，第${i}$件物品的重量为${weights[i]}$，价值为${values[i]}$，求解将哪些物品装入背包可使价值总和最大。

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态只是1或0, 此问题称为01背包问题。

数据：物品个数${n=5}$,物品重量${weights=[2，2，6，5，4]}$,物品价值${values=[6，3，5，4，6]}$,背包总容量${W=10}$。

我们设置一个矩阵${f}$来记录结果，${f(i, j)}$ 表示可选物品为 ${i...n}$ 背包容量为 ${j(0 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]) } })

有${n}$件物品和${1}$个容量为W的背包。每种物品没有上限，第${i}$件物品的重量为${weights[i]}$，价值为${values[i]}$，求解将哪些物品装入背包可使价值总和最大。

最简单思路就是把完全背包拆分成01背包，就是把01背包中状态转移方程进行扩展，也就是说01背包只考虑放与不放进去两种情况，而完全背包要考虑 放0、放1、放2...的情况，

这个k当然不是无限的，它受背包的容量与单件物品的重量限制，即${j/weights[i]}$。假设我们只有1种商品，它的重量为20，背包的容量为60，那么它就应该放3个，在遍历时，就0、1、2、3地依次尝试。

程序需要求解${n*W}$个状态，每一个状态需要的时间为${O（W/w_i）}$，总的复杂度为${O(nW*Σ(W/w_i))}$。

我们再回顾01背包经典解法的核心代码