0/1 最低成本背包

Question

著名的0/1背包问题的重点是在给定的Weight (W).

中得到最大值cost/value

上面的代码是这样的::

n = cost_array / weight_array size
INIT :: fill 0th col and 0th row with value 0
for (int i=1; i<=n; i++) {
            for (int j=1; j<=W; j++) {
                if (weight[i-1] <= j) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i-1]] + cost[i-1]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

答案:: dp[n][W]

新问题 :: 因此，我们在这里计算最大值 cost/value。但是，如果我想找到最小值 cost/value 怎么办（它仍然仅限背包）。

我认为问题归结为我如何执行上面的 INIT 步骤。正如在循环中一样，我认为它将保持不变，唯一的区别是 Math.max 变为 Math.min

我用 Infinity、0 等尝试了 INIT 步骤，但无法构建迭代解决方案。我们怎么可能那样做？

Answer 1

写@radovix提到的答案

将每个权重转换为负数并编写相同的算法。

Answer 2

这是一个用 JS 编写的有效算法（最小成本最大背包），时间复杂度为 O(nC) 和 space 复杂度为 O(n+C)，而不是 [= 的明显解决方案19=] 具有 DP 矩阵的复杂度 O(nC)。给定一个背包实例 (I, p,w, C)，MCMKP（Minimum-Cost Maximal Knapsack Packing）的目标是找到一个最大的背包包装 S⊂I，使所选物品的利润最小化

    const knapSack = (weights, prices, target, ic) => {
      if (weights.length !== prices.length) {
        return null;
      }
      let weightSum = [0],
      priceSum = [0];
      for (let i = 1; i < weights.length; i++) {
        weightSum[i] = weights[i - 1] + weightSum[i - 1];
        priceSum[i] = prices[i - 1] + priceSum[i - 1];
      }
      let dp = [0],
      opt = Infinity;
      for (let i = 1; i <= target; i++) dp[i] = Infinity;
      for (let i = weights.length; i >= 1; i--) {
        if (i <= ic) {
          const cMax = Math.max(0, target - weightSum[i - 1]),
          cMin = Math.max(0, target - weightSum[i - 1] - weights[i - 1] + 1);
          let tmp = Infinity;
          for (let index = cMin; index <= cMax; index++) {
            tmp = Math.min(tmp, dp[index] + priceSum[i - 1]);
          }
          if (tmp < opt) opt = tmp;
        }
        for (let j = target; j >= weights[i - 1]; j--) {
          dp[j] = Math.min(dp[j], dp[j - weights[i - 1]] + prices[i - 1]);
        }
      }
      return opt;
    };
    
    knapSack([1, 1, 2, 3, 4],[3, 4, 6, 2, 1],5,4);

在上面的以下代码中，我们将关键项目定义为一个项目，其权重给出了任何可行解决方案中遗漏的最小可能项目的严格上限。关键项的索引，即第一个超出容量的项的索引，假设所有 i ≤ ic 也会被带走。 opt 是最优解。观察项目 {1, . . . , i − 1} 确定背包的剩余容量（以 cMax 形式给出）必须使用来自 {i + 1, . . . , n}, 而 cMin 是由以下事实决定的：包装必须是最大的，而第 i 项是从解决方案中取出的最小项

0/1 最低成本背包

0/1 Knapsack with Minimum Cost

knapsack-problem

dynamic-programming