0/1 背包问题的最小成本

Question

0/1 背包问题的最小成本

4

著名的 0/1 背包问题专注于在给定重量（Weight (W)）中获得最大价值。

上述问题的代码如下：

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]

新问题 :: 我们现在要求最小成本/价值。但是如果我想要找到最小成本/价值呢（仍然是有界背包）。

我认为问题归结为如何执行上面的INIT步骤。对于循环，我认为唯一的区别是Math.max变成了Math.min。

我尝试过使用Infinity、0等来进行INIT步骤，但是我无法构建迭代式解决方案。我们怎么可能做到这一点呢？

- arqam

1

只需将每个权重转换为负数，不要更改算法。 - radovix

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- arqam · Answer 1

根据 @radovix 的提及编写答案

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

- Lahmedi Abderrahmen · Answer 2

here's an efficient algorithm for your problem written in JS (minimal-cost maximal knapsacking) with time complexity O(nC) and space complexity O(n+C) instead of the obvious solution with space complexity O(nC) with a DP matrix. Given a knapsack instance (I, p,w, C), the goal of the MCMKP (Minimum-Cost Maximal Knapsack Packing) is to find a maximal knapsack packing S⊂I that minimizes the profit of selected items

    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}确定了必须使用来自{i + 1，...，n}的项目填充的背包的剩余容量（给定为cMax），而cMin是由于装箱必须是最大化的且项目i是从解决方案中取出的最小项目所确定的。