CODEWITHSUNDEEP
c++knapsack-problem
Jacob Mutale
Jacob Mutale

Reputation: 57

segmentation fault knapsackproblem

I wrote this knapsack problem solution in c++ however when I run it, it gives me segmentation fault I have tried everything and my compiler will always give me the segmentation fault error.

#include<iostream>
#include<algorithm>

int knapsack(int v[],int w[],int n,int W)
{
    int V[n][W];
    for(int i = 0; i<=W;i++)
    {
        V[0][i] = 0;
    }
    for(int i = 0; i <= n; i++){
        for(int j = 1; j<=W; j++)
        {
            if(w[i]<=W)
            {
                V[i][j] = std::max(V[i-1][j], v[i]+V[i-1][j-w[i]]);
            }
            else
            {
                V[i][j] = V[i-1][j];
            }

        }
    }
    return V[n][W];
}

int main()
{
    int v[4] = {10,40,30,50};
    int w[4] = {5,4,6,3};
    int n = 3;
    int W = 10;

    std::cout<<"item value:"<<knapsack(v,w,n,W);
}

Upvotes: 1

Views: 209

Answers (2)

Lukas-T
Lukas-T

Reputation: 11350

  1. Don't use VLAs. The size of an array must be known at compile time, else it's not standard C++. Those are compiler extensions that are not portable and introduce some hidden costs.

  2. Array indices go from 0 to length-1. in you loop 

    for(int i = 0; i<=W;i++)

    i can reach W, then V[0][W] is out of bounds which causes the seg fault. You have to use < instead of <=: 

    for(int i = 0; i < W; i++)

  3. n should probably be 4, if it's meant to represent the size of the array, a std::vector would make your life easier here, because a vector knows it's size

  4. In general don't use C-style arrays or raw pointers at all in this day and age, use std::vector instead.

Upvotes: 2

Ismael Padilla
Ismael Padilla

Reputation: 5566

int V[n][W];
for(int i = 0; i<=W;i++)
{
    V[0][i] = 0;
}

Note that V's indexes go from V[0][0] to V[0][W-1]. Your for loop will try to read V[0][W].

The same error is repeated in other places. Your end condition in your for loops should be < (strictly less) instead of <= (less or equal than).

Upvotes: 1

Related Questions