题目描述

01背包问题-javascript的简单写法。

(动态规划-二维dp) 时间$O(n^2)$，空间$O(n^2)$

JavaScript 代码

var buf = '';
process.stdin.on('readable', function() {
  var chunk = process.stdin.read();
  if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
  const input = buf.split('\n').map((line) => line.split(' ').map((x) => parseInt(x)));
  const res = main(input);
  console.log(res);
});
function main(input) {
  const [N, V] = input.shift(); // N 是物品数量，V 是背包容量
  const dp = [];
  for (let i = 0; i <= N; i++) {
    dp[i] = Array.from({ length: V + 1 }).fill(0);
  }
  for (let i = 1; i <= N; i++) {
    const vi = input[i - 1][0]; // 第 i 件物品的体积
    const wi = input[i - 1][1]; // 第 i 件物品的价值
    for (let j = 1; j <= V; j++) {
      // j 表示容量
      if (vi > j) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vi] + wi);
      }
    }
  }
  return dp[N][V];
}

(动态规划-一维dp) 时间$O(n^2)$，空间$O(n)$

JavaScript 代码

var buf = '';
process.stdin.on('readable', function() {
  var chunk = process.stdin.read();
  if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
  const input = buf.split('\n').map((line) => line.split(' ').map((x) => parseInt(x)));
  const res = main(input);
  console.log(res);
});
function main(input) {
  const [N, V] = input.shift(); // N 是物品数量，V 是背包容量
  const dp = Array.from({ length: V + 1 }).fill(0);
  // i 表示第几个物品
  for (let i = 1; i <= N; i++) {
    const vi = input[i - 1][0]; // 第 i 件物品的体积
    const wi = input[i - 1][1]; // 第 i 件物品的价值
    // j 表示容量
    for (let j = V; j >= vi; j--) {
      dp[j] = Math.max(dp[j], dp[j - vi] + wi);
    }
  }
  return dp[V];
}