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
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!
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.
User contributions licensed under CC BY-SA 3.0