0/1 Knapsack with Minimum Cost

Question

The famous 0/1 knapsack problem focuses on getting the maximum cost/value in the given Weight (W).

The code for the above is this ::

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];
                }
            }
        }

Ans :: dp[n][W]

NEW Problem :: So, here we are calculating the maximum cost/value. But what if I want to find the minimum cost/value (Its still bounded knapsack only).

I think the problem boils down how I do the INIT step above. As in the loop I think it will remain same with the only difference of Math.max becoming Math.min

I tried the INIT step with Infinity, 0 etc but am not able to build the iterative solution. How can we possibly do that?

user_6366458 · Answer

Writing answer as mentioned by @radovix

Convert every weight to negative number and write the same algorithm.

user_7144490 · Answer

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);

In the following code above, we define a critical item, as an item whose weight gives a tight upper bound on the smallest possible item left out of any feasible solution. the index of the critical item, i.e., the index of the first item that exceeds the capacity, assuming all i ≤ ic will be taken as well. opt is the optimal solution. Observe that the items {1, . . . , i − 1} determine the remaining capacity of the knapsack (which is given as cMax) that has to be filled using items from {i + 1, . . . , n}, whereas cMin is determined by to the fact that the packing has to be maximal and that item i is the smallest one taken out of the solution

0/1 Knapsack with Minimum Cost

2 Answers