[JavaScript知识库]背包问题-JavaScript

一、0-1背包

1.1.题目描述

有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

//二维数组
function bag(w, v, s) {
  const dp = new Array(w.length + 1).map((item) => Array(s + 1).fill(0));
  for (let i = 1; i <= w.length; i++) {
    for (let j = 0; j <= s; j++) {
      if (w[i - 1] <= j) {
        dp[i][j] = Math.max(dp[i - 1][j], 
        dp[i - 1][j - w[i - 1]] + v[i - 1]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[(w.length, s)];
}
//一维数组
function bag(wight, value, size) {
  const len = wight.length, 
    dp = Array(size + 1).fill(0);
  for(let i = 1; i <= len; i++) {
    for(let j = size; j >= wight[i - 1]; j--) {
      dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);
    }
  }
  return dp[size];
}