多重背包理论

有N种物品和一个容量为V的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci，价值是Wi。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个 01 背包问题，因此，01 背包里面在加一个for循环遍历一个每种商品的数量，就可以解决了

let dp = new Array(bagWeight + 1).fill(0); // 初始化动态规划数组

for (let i = 0; i < n; i++) {
  // 遍历物品
  for (let j = bagWeight; j >= weight[i]; j--) {
    // 遍历背包容量
    // 以上为01背包，然后加一个遍历个数
    for (let k = 1; k <= nums[i] && j - k * weight[i] >= 0; k++) {
      // 遍历个数
      dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
    }
  }
}

携带矿石资源

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量w[i]，一个价值v[i]，以及最多k[i]个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

代码实现

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let lineCount = 0;
let c,
  n = 0;
let value = [];
let space = [];
let nums = [];
rl.on("line", function (line) {
  if (lineCount == 0) {
    var arr = line.split(" ").map(Number);
    c = arr[0];
    n = arr[1];
  } else if (lineCount == 1) {
    space = line.split(" ").map(Number);
  } else if (lineCount == 2) {
    value = line.split(" ").map(Number);
  } else if (lineCount == 3) {
    nums = line.split(" ").map(Number);
    const dp = new Array(c + 1).fill(0);
    for (let i = 0; i < n; i++) {
      for (let j = c; j >= space[i]; j--) {
        for (let k = 1; k <= nums[i] && j - k * space[i] >= 0; k++) {
          dp[j] = Math.max(dp[j], dp[j - space[i] * k] + value[i] * k);
        }
      }
    }

    console.log(dp[c]);
  }
  lineCount++;
});