Function not returning/Program exiting

Question

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

Advice: stop using C-style arrays and learn about (and use) `std::array` and `std::vector` instead. — Jesper Juhl, Jul 28 '20 at 20:26
I'm with Jesper here. You *urgently* need to kick this habit. This function leaks memory in a huge way each time it's run. This is not a sustainable way of developing code. You also need to learn how to do 2D array emulation with a simple 1D array. These are easier to allocate and much, much faster to access. — tadman, Jul 28 '20 at 20:29
When I use the debugger, it usually shows me exactly where the code crashes. Debugger is very useful! — anatolyg, Jul 28 '20 at 20:33

Daniel Jour · Accepted Answer · 2020-07-28T20:47:18.013


    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?

Would vector subscript being out of range be the same issue as trying to go past the bounds of the array? I changed them to vectors and remove the extra indexing, but it seems to still be a problem — CampinKiller, Jul 28 '20 at 21:51
Yes, out of range is out of range; when you have 5 elements there's no way you can access/use a sixth. Using `std::vector::at` instead of its `operator[]` gives you (guaranteed) bounds checking, which might be helpful in your situation — Daniel Jour, Jul 29 '20 at 10:49

score 0 · Answer 2 · answered Jul 28 '20 at 20:38

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 Jul 28 '20 at 20:38

utabasil

1

Function not returning/Program exiting

2 Answers2