Function not returning/Program exiting

0

I'm writing code for a dynamic solution to the knapsack problem, with the values, weight, etc being read in from a file. After writing the knapsack function code, it seems that it will not return when I try to test just the result being returned.

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

//knapsack here
int knapsack(int cap, int weight[], int value[], int n)
{
    int** K = new int* [n + 1];
    int j = 0;
    int l = 0;
    for (int i = 0; i < n + 1; i++)
    {
        K[i] = new int[cap + 1];
    }
    for (j = 0; j <= n; j++)
    {
        for (l = 0; l <= cap; l++)
        {
            if (j == 0 || l == 0)
                K[j][l] = 0;
            else if (weight[j - 1] <= l)
            {
                K[j][l] = max(weight[j - 1] + K[j - 1][l - weight[j - 1]], K[j - 1][l]);
            }
            else
            {
                K[j][l] = K[j - 1][l];
            }
        }
    }

    return K[j][l]; <--- Exception thrown
}

int main(void)
{
    string filename;
    ifstream infile;
    int capacity = 0;
    int items = 0;

    //Get input file from user and open

    cout << "Enter the file name: ";
    cin >> filename;

    infile.open(filename);

    //Get capacity and number of items
    infile >> capacity >> items;

    //Initialize arrays
    int* w = new int[items];
    int* v = new int[items];

    //Read values from file into arrays
    for (int i = 0; i < items; i++)
    {
        infile >> w[i];
        infile >> v[i];
    }

    //Solution Table
    cout << endl << endl << endl;
    cout << "Solution Table:" << endl;

    //Testing purposes
    cout << knapsack(capacity, w, v, items) << endl << "Test";

    infile.close();

    return 0;

}

Everything that is printed in main will print up until the final cout (after the Solution Table: line prints). The program will then pause for a moment and exit with an error code (C:\Users\Me\source\repos\Project3\Debug\Project3.exe (process 3028) exited with code -1073741819). I haven't been able to figure out a way to get a return from the function yet, and the exiting is something I haven't been able to figure out why it is occurring either.

EDIT: On using the debugger, an exception is being thrown when running through the knapsack function on the return:

Exception thrown at 0x006BB128 in Project3.exe: 0xC0000005: Access violation reading location 0xFDFDFE0D

c++
algorithm
knapsack-problem
asked on Stack Overflow Jul 28, 2020 by CampinKiller • edited Jul 28, 2020 by CampinKiller

2 Answers

1

    int** K = new int* [n + 1];
    // ...
        K[i] = new int[cap + 1];
    // ...
    for (j = 0; j <= n; j++)
    {
        for (l = 0; l <= cap; l++)
        {
            // ...
        }
    }
    // j == n + 1
    // l == cap + 1
    return K[j][l]; <--- Exception thrown because of out of bounds access to K

K is an array of length n + 1, which means its elements are accessed using indices from O to (inclusive) n. n + 1 is an out of bound access. At the end of the (outer) for loop the variable j is n + 1. You make the same error with the inner loop and the second operator[].

That being said, it helps a lot if you:

  • Ditch the idea of "2d arrays". These arrays of pointers to arrays are difficult to handle and have a heavy performance impact (messed up memory locality). They are (probably) only useful when the "full" array (e.g. the 2D table flattened into a single array) is too large to reliably get successfully allocated.

  • Use std::vector. There is really no point working with raw arrays. Except for learning. And in that case: delete[] the memory you allocate!

  • Why is "using namespace std;" considered bad practice?

answered on Stack Overflow Jul 28, 2020 by Daniel Jour • edited Jul 28, 2020 by Daniel Jour
0

C-style strings might cause problems. They are hard to maintain and track. I support Jesper's idea here.

Also, I do not see that you are freeing the memory after you are done with the pointers which will create memory leakage.

answered on Stack Overflow Jul 28, 2020 by utabasil

User contributions licensed under CC BY-SA 3.0