背包問題-JavaScript

文章目錄

• 一、0-1背包
• • 1.1.題目描述

一、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];
}