背包问题

根据维基百科，背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。

01背包问题
定一个背包，容量为V。一共有n件物品，第i件物品的价值为w[i]，体积为v[i]。求背包中能装入物品的价值总和最大为多少。
使用动态规划求解。设置dp[i][j]表示前i件物品，在总体积不超过j的情况下，价值总和最大为dp[i][j]。则有dp[0][0-V]=0。dp[0-n][0]=0。当i>0时，每一件物品都有装入和不装入两种状态，而装入的前提条件是v[i]<=背包剩余空间。则可以写出状态转移方程：

（1）if (j >= v[i]) , dp[i][j] = Math.max( dp[i - 1][ j - v[i-1] ] + w[i-1],dp[i-1][j] )。
（2）if(j<v[i]),dp[i][j]=dp[i-1][j]。

//通过状态转移方程写出代码：

function bag_01(w,v,V){
  let dp=[];
  // 初始化
  for(let i=0;i<=w.length;i++){
    dp[i]=[];
    dp[i][0]=0;
  }
  for(let i=0;i<=V;i++){
    dp[0][i]=0;
  }

  // 动态规划填表
  for(let i=1;i<=w.length;i++){
    for(let j=1;j<=V;j++){
      if(j>=v[i-1]){
        dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);
      }else{
        dp[i][j]=dp[i-1][j];
      }
    }
  }
  return dp[w.length][V];
}

由以上可以看出，dp[i][j]的状态取决于dp[i-1][j-v[i]]或者dp[i-1][j]，仅与dp[i-1]有关。则我们可以进行空间优化，每次只记录第二维的数据，后面循环的数据进行覆盖，每次dp[j]的值都是最新的值。则最后dp[V]的值就是我们想要的值。

let dp=[];
  // 初始化
  for(let i=0;i<=V;i++){
    dp[i]=0;
  }

  for(let i=1;i<=w.length;i++){
    for(let j=V;j>=1;j--){//防止前面的数据被覆盖，必须逆向填表
      if(j>=v[i-1]){
        dp[j]=Math.max(dp[j],dp[j-v[i-1]]+w[i-1]);
      }
    }
  }
  return dp[V];

完全背包问题
与01背包的不同之处在于，完全背包不同种的物品都有无限个。定一个背包，容量为V。一共有n种物品，第i种物品的价值为w[i]，体积为v[i]，每种物品有无限个。求背包中能装入物品的价值总和最大为多少。
此时与求解01背包问题类似，只不过状态转移方程改变了。

if(j>=v[i-1])  dp[i][j]=Math.max(dp[i-1][j],dp[i][j-v[i-1]]+w[i-1])
else dp[i][j]=dp[i-1][j]

//通过状态转移方程写出代码：

let dp=[];
  // 初始化
  for(let i=0;i<=w.length;i++){
    dp[i]=[];
    dp[i][0]=0;
  }
  for(let i=0;i<=V;i++){
    dp[0][i]=0;
  }

  // 动态规划填表
  for(let i=1;i<=w.length;i++){
    for(let j=1;j<=V;j++){
      if(j>=v[i-1]){
        dp[i][j]=Math.max(dp[i-1][j],dp[i][j-v[i-1]]+w[i-1]);//仅仅这里与01背包有区别
      }else{
        dp[i][j]=dp[i-1][j];
      }
    }
  }
  return dp[w.length][V];

完全背包也有空间优化手段，优化时需要正向填表，因为完全背包的dp[i][j]取决于dp[i][j-v[i-1]]和dp[i-1][j],则前面数据需要使用被覆盖后的数据。

let dp=[];
  // 初始化
  for(let i=0;i<=V;i++){
    dp[i]=0;
  }

  for(let i=1;i<=w.length;i++){
    for(let j=1;j<=V;j++){//需要考虑前面的数据被覆盖，必须正向填表
      if(j>=v[i-1]){
        dp[j]=Math.max(dp[j],dp[j-v[i-1]]+w[i-1]);
      }
    }
  }
  return dp[V];

多重背包问题
思路与01背包和完全背包大致相等，每种物品多了一个数量限制。定一个背包，容量为V。一共有n种物品，第i种物品的价值为w[i]，体积为v[i]，数量为N[i]。求背包中能装入物品的价值总和最大为多少。
状态转移方程变为：

if(j>=v[i-1]) 
for(let k=1;k<=Math.min(Math.floor(j/v[i]),N[i-1]);k++) {
  dp[i][j]=Math.max(dp[i-1][j],dp[i][j-k*v[i-1]]+w[i-1]*k
}

else dp[i][j]=dp[i-1][j]