5

Task

Given n gold bars, find the maximum weight of gold that fits into bag of capacity W

Input

first line contains the capacity W of the knapsack and the number n of bars of gold. The next line contains n integers

Output

The max weight of gold that fits into a knapsack of capacity W.

Constraints

1 <= W <= 10000; 1<= n <= 300; 0 <= w0, w1, w2, ... , w(n-1) <= 100000

Code

#include <iostream>
#include <vector>
using std::vector;

int optimal_weight(int W, vector<int> w) {
  int n = w.size() + 1;
  int wt = W + 1;
  int array [n][wt];
  int val = 0;

  for(int i = 0; i < wt; i++) array [0][i] = 0;
  for(int i = 0; i < n; i++) array [i][0] = 0;

  for(int i = 1; i< n; i++) {
    for(int j = 1; j < wt; j++ ){
      array[i][j] = array [i-1][j];
      if (w[i-1] <= j) {
        val = array[i-1][j - w[i-1]] + w[i-1];
        if(array[i][j] < val) array[i][j] = val;
      }
    }
  }

  //printing the grid
  // for(int i=0; i < n; i++) {
  //   for(int j=0; j < wt; j++) {
  //     cout<<array[i][j]<<" ";
  //   }
  //   cout<<endl;
  // }
  // cout<<endl;

  return array [n-1][wt-1];
}

int main() {
  int n, W;
  std::cin >> W >> n;
  vector<int> w(n);
  for (int i = 0; i < n; i++) {
    std::cin >> w[i];
  }
  std::cout << optimal_weight(W, w) << '\n';
}

The above code works fine for smaller inputs, but gives an unknown signal 11 error on the platform I wish to submit to. My best guess is of a possible segmentation fault, but I have been unable to debug it since quite some time now. Any help is much appreciated!

Community
  • 1
  • 1

2 Answers2

7

First note that your code doesn't work. That is, it doesn't compile when you adhere strictly to the C++ language standard, as C++ does not support variable-length arrays. (as noted by @Evg in a comment; some compilers offer this as an extension.)

The main reason for excluding those from C++ is probably why you're experiencing issues for larger problem sizes: the danger of stack overflows, the namesake of this website (as noted by @huseyinturgulbuyukisik in a comment). Variable-length arrays are allocated on the stack, whose size is limited. When you exceed it, you might attempt to write to a segment of memory that is not allocated to your process, triggering Linux signal 11, also known as SIGSEGV - the segmentation violation signal.

Instead of stack-based allocation, you should allocate your memory on the heap. A straightforward way to do so would be using the std::vector container (whose default allocator does indeed allocate on the heap). Thus, you would write:

 std::vector<int> vec(n * wt);

and instead of array[i][j] you'd use vec[i * wt + j].

Now, this is not as convenient as using array[x][y]; for the extra convenience you can, for example, write a helper lambda, to access individual elements, e.g.

auto array_element = [&vec, wt](int x, int y) { return vec[x * wt + y]; }

with this lambda function available, you can now write statements such as array_element(i,j) = array_element(i-1,j);

or use a multi-dimensional container (std::vector<std::vector<int>> would work but it's ugly and wasteful IMHO; unfortunately, the standard library doesn't have a single-allocation multi-dimensional equivalent of that).

Other suggestions, not regarding a solution to your signal 11 issue:

  • Use more descriptive variable names, e.g. weight instead of wt and capacity instead of W. I'd also considersub_solutions_table or solutions_table instead of array, and might also rename i and j according to the semantics of the dynamic solution table.
  • You never actually need more than 2 rows of the solutions table; why not just allocate one row for the current iteration and one row for the previous iteration, and have appropriate pointers switch between them?
einpoklum
  • 118,144
  • 57
  • 340
  • 684
1

Replace

vector< vector< int> >  k(n + 1,vector< int>(W + 1));

with 

int array[n][w];
user2738882
  • 1,161
  • 1
  • 20
  • 38
Ashish Dukare
  • 11
  • 1