0-1 Integer Knapsack returning wrong answer (Dynamic Programming)

Question

The title is pretty self-explanatory, I've been fiddling it for a couple of days now. What is the stupid thing that I'm doing wrong? The problem is for a bunch of materials that are the same weight and thus doesn't have an input vector for values, so it might be the fact that I'm not adding a value in the std::max part, but I've tried doing that and haven't gotten the right answer either. W is the capacity of the knapsack, w is a vector consisting of the weights of the items.

#include <iostream>
#include <vector>

using std::vector;
using std::max;

int optimal_weight(int W, const vector<int> &w) {
     size_t size = w.size();
     int knapsack[size+1][W+1];

     for (size_t a = 0; a <= size; a++) {
         knapsack[a][0] = 0;
     }

     for (int b = 0; b <= W; b++) {
         knapsack[0][b] = 0;
     }

     for (size_t i = 1; i <= size; i++) {
          for (int j = 0; j <= W; j++) {
                   knapsack[i][j] = knapsack[i-1][j];

                   if (w[i-1] <= j) {
                          knapsack[i][j] = std::max(knapsack[i-1][j-w[i-1]], knapsack[i-1][j]);
                    }

                }
         }
      return knapsack[size][W];
    }

Can you give an example input, expected and actual output? Also, can you please provide a minimal reproducible example? — mindriot

uSeemSurprised uSeemSurprised · Accepted Answer · 2016-04-05T10:53:12

The line in the code : int knapsack[size][W+1]

should be changed to : int knapsack[size+1][W+1]

It is because arrays are indexed from 0, and in the above case defined for 0 to size-1 and you are accessing the element at index = size. Also add the corresponding weights while calculating std::max.

0-1 Integer Knapsack returning wrong answer (Dynamic Programming)

1 Answers