题目描述

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

从大到小

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--) {
      // k 表示第 i 件物品取多少次
      for(let k = 0; k*vi <= j; k++){
        dp[j] = Math.max(dp[j], dp[j - k*vi] + k*wi);
      }
    }
  }
  return dp[V];
}

从小到大

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 = vi; j <= V; j++) {
      dp[j] = Math.max(dp[j], dp[j - vi] + wi);
    }
  }
  return dp[V];
}