I have a C++ program that works ok with one data set (3 records) but throws an "Access Violation" error with another data set (10 records).

The two data sets (incl. snapshots of the program output) are attached in the XLS.

The C++ code is shown below. [Note: I also changed the line >> #define MAX 10 << from/to >> #define MAX 900 <<. Then however, I get a "stack overflow" error.

My question: How can I fix the C++ code so that I won't get the "Access Violation" error when using scenario #2.

Thanks,
EEH

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <math.h> #include <limits.h>using namespace std;#define MAX 10class knapsack{ private : int n, capacity, value[MAX][MAX]; struct object { int weight; int value; } obj[MAX]; public : void getdetails(int &, int &); void initialise(); int mfknapsack(int, int); void display(int);};void knapsack :: getdetails(int &no, int &cap){ int i; cout << "\nEnter the number of objects: "; cin >> n; no = n; cout << "\nEnter the maximum capacity of the Knapsack: "; cin >> capacity; cap = capacity; cout << "\nEnter the Weights and Values of " << n << " objects\n"; for (i = 1; i <= n; i++) { cout << endl; cout << "Weight[" << i << "] = "; cin >> obj[i].weight; cout << "Value[" << i << "] = "; cin >> obj[i].value; }}void knapsack :: initialise(){ int i, j; for (i = 0; i <= n; i++) for (j = 0; j <= capacity; j++) { if (i == 0 || j == 0) value[i][j] = 0; else value[i][j] = -1; }}int knapsack :: mfknapsack(int n, int c){ int val, temp, temp1; if (value[n][c] < 0) { temp = mfknapsack(n - 1, c); if (c < obj[n].weight) val = temp; else { temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight); if (temp1 > temp) val = temp1; else val = temp; } value[n][c] = val; } return (value[n][c]);}void knapsack :: display(int cost){ int i, next, cap; cout << "\nThe objects included in the optimal subset are: "; next = n; cap = capacity; for (i = n; i > 0; i--) { if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; } cout << "\n\nThe maximum profit obtained is: "; cout << cost;}int main(){ int profit, no, cap; knapsack k; k.getdetails(no, cap); k.initialise(); profit = k.mfknapsack(no, cap); k.display(profit); system("pause"); return 0;}

i read some about knapsack problem and found an algorithm that doesn't use recursion. in my opinion tthat isn't much a difference cause recursive algorithm calls mfknapsack(r-1, c), so actually it is a loop backwards from n-1 to 0.

U is the set of objects objects with w(eight) and v(alue) property
B is the capacity (integer only)

Input: U, B, w, v
R := [1…(n+1), 0…B]-Matrix all cells initially 0
FOR i = n … 1
FOR j = 1 … B
IF w(i) <= j
R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )
ELSE
R[i,j] := R[i+1,j]
Output: R[1,B]

you see matrix R has dimensions n+1, B what explains the out-of-boundary access when the matrix has only MAX x MAX dimensions.

you see outer loop starts with row n (== index n-1) (what is equivalent to initial call of mfknapsack(no-1, cap-1)) and goes backwards until 1 (index 0).

the final (best) result is in R[1, B] what is row number 0 and column cap-1 but it needs some kind of backtracking to actually determine which objects have been included to the optimum (must not be unique).

i am not quite sure whether it is easier to write the code newly from that algorithm or try to correct the current code which unfortunately has some basic lacks in dimensioning and accessing of rows and columns.

You should be looping 0 to n-1 (preferred), or use i-1 as your index instead of i (not recommended).

Line 36 is the problem: for (i = 1; i <= n; i++)

Unlike BASIC, array indices start at zero in C.

You should review the rest of your code to make sure this is the paradigm you are using.

0

ExpExchHelpAuthor Commented:

sjklein42:

Thanks... I appreciate the feedback. I'm really a novice in C++. I found this code online and would like to modify it.

Are you indicating that the code is written in BASIC? If yes, could you pls provide me some support for modifying it?

Thousand thanks in advance!!

EEH

0

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

Hi. My reference to BASIC was more historical than technical. I was just trying to imagine why you wanted to start the array at 1 instead of zero.

I see that it is so the end-user sees the prompts starting with Weight[1] instead of Weight[0]. But your code still needs to index the obj array starting at zero.

So do this in your input loop. See the "-1" I added to two lines?

for (i = 1; i <= n; i++) { cout << endl; cout << "Weight[" << i << "] = "; cin >> obj[i-1].weight; cout << "Value[" << i << "] = "; cin >> obj[i-1].value; }

Somewhere you are indexing "obj" with a 10 when the maximum valid index is 9.

As a general technique to debug this, add some temporary tracing code using cout calls before every reference to "obj" to show the value of the index you are using.

I worry about lines 65 and 69 in particular. The first time that mfknapsack is called, is "n" equal to 10 or 9? If 10, then you have a problem using obj[n] in those places.

0

ExpExchHelpAuthor Commented:

sjklein42:

Thanks... I've added the debug statement. Pls see attached JPG for console output.

I'm not sure though how this might help me.

You indicated that there might be an issue w/ lines 65 and 69. I hope you won't mind continuing to provide additional support for helping me figure this one out.

Have you tried entering those two data sets? Based on those values (max capacity of 5 vs. max capacity of 900), does something else need to be adjusted?

We can see there is problem even with the output you have provided.

Consider the debug line that says
"debugging n = 3"

This is when you have only three input values.

When you have 10 input values, you would probably see a line that says:
"debugging n = 10"

However you are only allowed to index into the obj array with zero through 9.

When indexing into obj with a 10, you will get an ACCVIO.

In at least one place in your code you are "off-by-one".

This can be tricky to debug but it is very common. You need to walk through the logic when "no" equals 10 to make sure that you aren't trying to use any obj index value beyond 9.

First, in the case of ten elements, you need to decide if you want to call mfknapsack with "no" (10), or "no-1" (9).

It could be as simple as this to avoid the ACCVIO, but it doesn't mean the rest of the code is right. You need to be careful you don't fall off the beginning of the array, too, by trying to index into the obj array with a value of (-1).:

profit = k.mfknapsack(no-1, cap);

Once you made this (more-or-less arbitrary) design decision of whether to call mfknapsack with no or no-1, walk through the rest of your code and make other changes as needed. Start with the case where no=1 and then walk through one iteration when no=10.

You are looking for places where you index into the obj array - make sure the index value is in range.

0

ExpExchHelpAuthor Commented:

sjklein42:

Thank you for the valuable feedback. I'm try my best... I'm afraid though that you've lost me in some of the technical jargon. I'm still learning C++... as mentioned, I came across this code and would like to modify it instead of creating something from scratch.

Is there any chance you are willing to provide me more specific help w/ the debugging?

Again, I appreciate your assistance in this matter.

EEH

0

ExpExchHelpAuthor Commented:

sjklein42:

Forgot something... (btw, see previous post first).

It appears that I can enter 10 data sets w/o problem as long as the MAX (capacity) value does NOT exceed "10". I added some random data values ranging between 1 and 10 (for both value and weight). In such case, the access violation did NOT appear.

So, maybe you already knew this... but I just realized that's not the # of data sets that causing the problem... it the max weight capacity.

Does this change anything for making the trouble-shooting easier?

On line 104 you call mfknapsack with the value no=10.

Looking into the mfknapsack routine, right away you have a bug. When you index into value[n] with n==10 it will fail because the lastvalid entry is value[9].

I tried a data set w/ small values (value & weight) again. It still "blows up". I noticed however that a "yellow arrow" was point at line #88. See snapshot below.

The Initialize routine will ACCVIO if capacity is 10 on line 55.

Assuming n can go up to 10 and capacity can go up to 10, you want to stop your loop with "<" tests instead of "<=" test.

Check the rest of your code for this bug.

This routine corrected:

void knapsack :: initialise(){ int i, j; for (i = 0; i < n; i++) for (j = 0; j < capacity; j++) { if (i == 0 || j == 0) value[i][j] = 0; else value[i][j] = -1; }}

I made the remaining modifications as well. It executes fine w/ data sets containing small values for weight and value.

Now, I tried the 2nd "scenario" with a weight capacity of 900 again. At this time, it is (original) line #104 that throws an error. At least I'm only a few lines away from the "finish line".

For the same reason as before, on line 62 the use of "cap" equal to 10 will also ACCVIO. Maximum valid index is 9 for an array with 10 entries.
:
line 86 could be changed like this. It will avoid this particular ACCVIO but we may not be done. I have a feeling we've just covered over a logic bug. But first let's get rid of the ACCVIOs and then see if it gives the right answers or not.

First, allow me to mention that I truly appreciate your patience w/ me. Working w/ experts like you make using this forum truly the "best place" on the web.

I hear you... and I just made that change again. Besides getting ride of the errors, I must keep the "optimal solution" in mind.

Based on the two original data sets (in XLS), let's focus on data set #1.
- 3 items
- Capacity of 5
- Values for [1]: 3, 5
- Values for [2]: 2, 3
- Values for [3]: 1, 4

Knowing what the optimal answer is (3, 1), we can quickly verify this on a piece of paper. It makes sense to select record 1 & 3... C++ outputs them as "3 1" in the original code.

Now, once I made some of these changes, I did not always "test" the answer of (3, 1... or 1, 3). I just that a moment ago.

I went back to the original solution and made your changes, tested the answer, and then ran the test again.

It appears that some of the "-1" modifications change the optimal answer. Depends where the (-1) was added, I come up with a solution of (2, 1) or (just 1).

So, again, I must keep the "known" solution in mind. It's somewhat time-consuming as the data set #1 solution does NOT blow up. Once I try scenario #2, I get the Access error.

I want to make sure that I don't overlook any of your steps. I wish I could toggle back and forth between the two data sets (hard coded in the declaration phase.... vs. using the CIN method). But I'm sure I can fix that later.

For right now, I'm starting w/ the original solution (giving me << 3, 1 >> as the optimal solution)... in hopes to make the code changes to that I can add the 900 weight capacity values.

Sorry for this long reply... it's just frustrating that I'm gaining ground on fixing execution errors but then end up with the (potentially) wrong solution.

Thoughts/recommendations?

EEH

0

ExpExchHelpAuthor Commented:

sjklein42:

First, allow me to mention that I truly appreciate your patience w/ me. Working w/ experts like you make using this forum truly the "best place" on the web.

I hear you... and I just made that change again. Besides getting ride of the errors, I must keep the "optimal solution" in mind.

Based on the two original data sets (in XLS), let's focus on data set #1.
- 3 items
- Capacity of 5
- Values for [1]: 3, 5
- Values for [2]: 2, 3
- Values for [3]: 1, 4

Knowing what the optimal answer is (3, 1), we can quickly verify this on a piece of paper. It makes sense to select record 1 & 3... C++ outputs them as "3 1" in the original code.

Now, once I made some of these changes, I did not always "test" the answer of (3, 1... or 1, 3). I just that a moment ago.

I went back to the original solution and made your changes, tested the answer, and then ran the test again.

It appears that some of the "-1" modifications change the optimal answer. Depends where the (-1) was added, I come up with a solution of (2, 1) or (just 1).

So, again, I must keep the "known" solution in mind. It's somewhat time-consuming as the data set #1 solution does NOT blow up. Once I try scenario #2, I get the Access error.

I want to make sure that I don't overlook any of your steps. I wish I could toggle back and forth between the two data sets (hard coded in the declaration phase.... vs. using the CIN method). But I'm sure I can fix that later.

For right now, I'm starting w/ the original solution (giving me << 3, 1 >> as the optimal solution)... in hopes to make the code changes to that I can add the 900 weight capacity values.

Sorry for this long reply... it's just frustrating that I'm gaining ground on fixing execution errors but then end up with the (potentially) wrong solution.

I am happy to help. Please post the entire source code as it stands now. I have lost track of which changes you have made.

0

ExpExchHelpAuthor Commented:

Quick follow-up.... pls see previous posting first.

I ran it with 10 data sets... all small values. See attached JPG for feedback. The output makes sense as "4 + 4" gives me the greatest value.

The code for this output is attached below. Again, some of the recommended changes had to be undone given that they causes an erroneous optimal value. [Right now, I'm still trying to figure out which change to keep and which ones to omit in order to not produce an incorrect optimal solution].

Anyhow, the answer of (8, 6) -- with optimal value of "8" is based on the code below. However, once it executes, I get an "dbhook.c" file popping up. I have no clue what that means... but I'm sure it aint "good news". I've also attached that file.

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <math.h> #include <limits.h>using namespace std;#define MAX 10class knapsack{ private : int n, capacity, value[MAX][MAX]; struct object { int weight; int value; } obj[MAX]; public : void getdetails(int &, int &); void initialise(); int mfknapsack(int, int); void display(int);};void knapsack :: getdetails(int &no, int &cap){ int i; cout << "\nEnter the number of objects: "; cin >> n; no = n; cout << "\nEnter the maximum capacity of the Knapsack: "; cin >> capacity; cap = capacity; cout << "\nEnter the Weights and Values of " << n << " objects\n"; for (i = 1; i <= n; i++) { cout << endl; cout << "Weight[" << i << "] = "; cin >> obj[i].weight; cout << "Value[" << i << "] = "; cin >> obj[i].value; }}void knapsack :: initialise(){ int i, j; for (i = 0; i <= n; i++) for (j = 0; j <= capacity; j++) { if (i == 0 || j == 0) value[i][j] = 0; else value[i][j] = -1; }}int knapsack :: mfknapsack(int n, int c){ int val, temp, temp1; if (value[n][c] < 0) { temp = mfknapsack(n - 1, c); if (c < obj[n].weight) val = temp; else { temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight); if (temp1 > temp) val = temp1; else val = temp; } value[n][c] = val; } return (value[n][c]);}void knapsack :: display(int cost){ int i, next, cap; cout << "\nThe objects included in the optimal subset are: "; next = n; cap = capacity; for (i = n; i > 0; i--) { if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; } cout << "\n\nThe maximum profit obtained is: "; cout << cost;}int main(){ int profit, no, cap; knapsack k; k.getdetails(no, cap); k.initialise(); profit = k.mfknapsack(no, cap); //profit = k.mfknapsack(no-1, cap-1); // commented out k.display(profit); system("pause"); return 0;}

The code (previous post) gives me the the correct solution when using the following:

- 3 items
- Capacity of 5
- Values for [1]: 3, 5
- Values for [2]: 2, 3
- Values for [3]: 1, 4

Also, as shown in the snapshot (when using 10 items), the solution of (8, 6) makes sense to me as well. From that perspective, I produce the correct optimal solution.

Trouble is though, when I the following data set:
- 10 items
- Capacity of 900
- Values for [1]: 100, 150
- Values for [2]: 200, 250
- Values for [3]: 200, 450
- Values for [4]: 200, 150
- Values for [5]: 200, 50
- Values for [6]: 200, 350
- Values for [7]: 200, 175
- Values for [8]: 200, 275
- Values for [9]: 400, 275
- Values for [1]: 400, 575

It would be like "Christmas" to me if I can execute this data set w/o having the program blow up.

EEH

0

ExpExchHelpAuthor Commented:

Made an error in the last value...
should be >> - Values for [10]: 400, 575 <<

You are still having trouble with your off-by-ones. Like in this fragment of your display code, you set next to n (which may be 10) and cap to capacity (which also may be 10) and then look at value[next][cap], which is value[10][10], but remember that the maximum allowable index into the value array is 9, like value[9][9]. This is because the index range goes from zero to nine which is ten values which is the size of the array. So this code will ACCVIO when passed n=10 or cap=10. This particular routine I did not fix since I am not sure what it is supposed to do exactly.

next = n; cap = capacity; for (i = n; i > 0; i--) { if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; }

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <math.h> #include <limits.h>using namespace std;#define MAX 10class knapsack{ private : int n, capacity, value[MAX][MAX]; struct object { int weight; int value; } obj[MAX]; public : void getdetails(int &, int &); void initialise(); int mfknapsack(int, int); void display(int);};void knapsack :: getdetails(int &no, int &cap){ int i; cout << "\nEnter the number of objects: "; cin >> n; no = n; cout << "\nEnter the maximum capacity of the Knapsack: "; cin >> capacity; cap = capacity; cout << "\nEnter the Weights and Values of " << n << " objects\n"; for (i = 1; i <= n; i++) { cout << endl; cout << "Weight[" << i << "] = ";>>>>> cin >> obj[i-1].weight; cout << "Value[" << i << "] = ";>>>>> cin >> obj[i-1].value; }}void knapsack :: initialise(){ int i, j;>>>>> for (i = 0; i < n; i++)>>>>> for (j = 0; j < capacity; j++) { if (i == 0 || j == 0) value[i][j] = 0; else value[i][j] = -1; }}>>>>>int knapsack :: mfknapsack(int count, int cap){ int val, temp, temp1;>>>>> int n = count - 1;>>>>> int c = cap - 1; if (value[n][c] < 0) { temp = mfknapsack(n - 1, c); if (c < obj[n].weight) val = temp; else { temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight); if (temp1 > temp) val = temp1; else val = temp; } value[n][c] = val; } return (value[n][c]);}void knapsack :: display(int cost){ int i, next, cap; cout << "\nThe objects included in the optimal subset are: ";>>>>> I can't figure out what you are trying to do exactly, but I know that this won't work the way you have it.>>>>> next = n - 1;>>>>> cap = capacity - 1;>>>>> for (i = n; i > 0; i--) {>>>>> if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; } cout << "\n\nThe maximum profit obtained is: "; cout << cost;}int main(){ int profit, no, cap; knapsack k; k.getdetails(no, cap); k.initialise(); profit = k.mfknapsack(no, cap); //profit = k.mfknapsack(no-1, cap-1); // commented out k.display(profit); system("pause"); return 0;}

I also suggest you have two different "MAX" variables. The maximum capacity is not really related to MAX_N and in fact could be greater than the number of items.

Small change:

#define MAX_N 10#define MAX_CAP 50class knapsack{ private : int n, capacity, value[MAX_N][MAX_CAP]; ...

expexchhlp, it took m some time to read all comments but i must assess you were still using wrong loop indices in your last code posted though siklein42 has told you multiple times that is was wrong.

in line 37 you have

for (i = 1; i <= n; i++)

while the correct statement is

for (i = 0; i < n; i++)

in line 50/51 you have

for (i = 0; i <= n; i++)
for (j = 0; j <= capacity; j++)

where it must be

for (i = 0; i < MAX; i++)
for (j = 0; j < MAX; j++)

note the function initialize should initialize all elements of value and not only up to the n or capacity.

in line 87 you have

next = n;
cap = capacity;
for (i = n; i > 0; i--)

where it must be

next = n-1;
cap = capacity-1;
for (i = n-1; i > 0; i--)

the reason why this loop must have only (n-1) iterations is that you compare value[next][cap] with value[next - 1][cap]). and you have to start with n-1 and cap-1 or your indices go out of boundary for n == MAX or capacity == MAX

in line 60 you have

int knapsack :: mfknapsack(int n, int c)

where you should use different name for first argument cause n already is name of member variable

int knapsack :: mfknapsack(int r, int c)

of course you would need to change the n to r in the following code lines.

note all i objected was multiple mentioned by siklein42 and there is no chance to get your program work if you don't apply all those changes and post the resulting code.

Sara

0

ExpExchHelpAuthor Commented:

sjklein42:

Again, thanks for providing the additional feedback. I'll check it out right now.

BREAK

Sara:

I also would like to thank you as well for chiming in... 'much appreciated. Are you comments based on which baseline code:

I've applied code changes from the following post:

http://#34940516
1. first all code lines 1 through 116 (second code example)
2. followed by additional modifications lines 1 through 11 (first code example)

Both versions through the ACCVIO error. I'm now looking into code recommendations (http://#34940602).

EEH

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <math.h> #include <limits.h>using namespace std;#define MAX 10class knapsack{ private : int n, capacity, value[MAX][MAX]; struct object { int weight; int value; } obj[MAX]; public : void getdetails(int &, int &); void initialise(); int mfknapsack(int, int); void display(int);};void knapsack :: getdetails(int &no, int &cap){ int i; cout << "\nEnter the number of objects: "; cin >> n; no = n; cout << "\nEnter the maximum capacity of the Knapsack: "; cin >> capacity; cap = capacity; cout << "\nEnter the Weights and Values of " << n << " objects\n"; for (i = 1; i <= n; i++) { cout << endl; cout << "Weight[" << i << "] = "; cin >> obj[i-1].weight; // sjklein42's recommendation cout << "Value[" << i << "] = "; cin >> obj[i-1].value; // sjklein42's recommendation }}void knapsack :: initialise(){ int i, j; for (i = 0; i < n; i++) // sjklein42's recommendation for (j = 0; j < capacity; j++) // sjklein42's recommendation { if (i == 0 || j == 0) value[i][j] = 0; else value[i][j] = -1; }}int knapsack :: mfknapsack(int count, int cap) // sjklein42's recommendation{ int val, temp, temp1; int n = count - 1; // sjklein42's recommendation int c = cap - 1; // sjklein42's recommendation if (value[n][c] < 0) { temp = mfknapsack(n - 1, c); if (c < obj[n].weight) val = temp; else { temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight); if (temp1 > temp) val = temp1; else val = temp; } value[n][c] = val; } return (value[n][c]);}void knapsack :: display(int cost){ int i, next, cap; cout << "\nThe objects included in the optimal subset are: "; // I can't figure out what you are trying to do exactly, but I know that this won't work the way you have it. // sjklein42's comment // next = n - 1; // sjklein42's recommendation //cap = capacity - 1; // sjklein42's recommendation // //for (i = n; i > 0; i--) // sjklein42's recommendation //{ // if (value[next][cap] != value[next - 1][cap]) // sjklein42's recommendation // { // cout << i << " "; // cap -= obj[i].weight; // } // next = i - 1; //} // sjklein42's recommendation (full replacement of next 11 lines -- change from above) next = n; cap = capacity; for (i = n; i > 0; i--) { if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; } cout << "\n\nThe maximum profit obtained is: "; cout << cost;}int main(){ int profit, no, cap; knapsack k; k.getdetails(no, cap); k.initialise(); profit = k.mfknapsack(no, cap); //profit = k.mfknapsack(no-1, cap-1); // EEH's comment k.display(profit); system("pause"); return 0;}

sarabande -- 'just getting ready to look into your recommendation. I presume your recommendations were based on code providing in posting http://#34940371. Or did you base it on sjklein42's code (http://#34940516)?

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <math.h> #include <limits.h>using namespace std;// #define MAX 10 // Replaced per sjklein42's recommendation#define MAX_N 10 // sjklein42's recommendation#define MAX_CAP 50 // sjklein42's recommendationclass knapsack{ //private : int n, capacity, value[MAX][MAX]; private : int n, capacity, value[MAX_N][MAX_CAP]; struct object { int weight; int value; //} obj[MAX]; // Replaced per sjklein42's recommendation } obj[MAX_N]; // sjklein42's recommendation public : void getdetails(int &, int &); void initialise(); int mfknapsack(int, int); void display(int);};void knapsack :: getdetails(int &no, int &cap){ int i; cout << "\nEnter the number of objects: "; cin >> n; no = n; cout << "\nEnter the maximum capacity of the Knapsack: "; cin >> capacity; cap = capacity; cout << "\nEnter the Weights and Values of " << n << " objects\n"; for (i = 1; i <= n; i++) { cout << endl; cout << "Weight[" << i << "] = "; cin >> obj[i-1].weight; // sjklein42's recommendation cout << "Value[" << i << "] = "; cin >> obj[i-1].value; // sjklein42's recommendation }}void knapsack :: initialise(){ int i, j; for (i = 0; i < n; i++) // sjklein42's recommendation for (j = 0; j < capacity; j++) // sjklein42's recommendation { if (i == 0 || j == 0) value[i][j] = 0; else value[i][j] = -1; }}int knapsack :: mfknapsack(int count, int cap) // sjklein42's recommendation{ int val, temp, temp1; int n = count - 1; // sjklein42's recommendation int c = cap - 1; // sjklein42's recommendation if (value[n][c] < 0) { temp = mfknapsack(n - 1, c); if (c < obj[n].weight) val = temp; else { temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight); if (temp1 > temp) val = temp1; else val = temp; } value[n][c] = val; } return (value[n][c]);}void knapsack :: display(int cost){ int i, next, cap; cout << "\nThe objects included in the optimal subset are: "; // I can't figure out what you are trying to do exactly, but I know that this won't work the way you have it. // sjklein42's comment // next = n - 1; // sjklein42's recommendation //cap = capacity - 1; // sjklein42's recommendation // //for (i = n; i > 0; i--) // sjklein42's recommendation //{ // if (value[next][cap] != value[next - 1][cap]) // sjklein42's recommendation // { // cout << i << " "; // cap -= obj[i].weight; // } // next = i - 1; //} // sjklein42's recommendation (full replacement of next 11 lines -- change from above) next = n; cap = capacity; for (i = n; i > 0; i--) { if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; } cout << "\n\nThe maximum profit obtained is: "; cout << cost;}int main(){ int profit, no, cap; knapsack k; k.getdetails(no, cap); k.initialise(); profit = k.mfknapsack(no, cap); //profit = k.mfknapsack(no-1, cap-1); // EEH's comment k.display(profit); system("pause"); return 0;}

Sorry... 'messed up the reference links again. See code and snapshots in the previous post. The message should have read:

sjklein42:
I made the code changes per http:#34940602 Still get an error. See snapshots.

BREAK

sarabande -- 'just getting ready to look into your recommendation. I presume your recommendations were based on code providing in posting http:#34940371. Or did you base it on sjklein42's code (http:#34940516)?

0

ExpExchHelpAuthor Commented:

Sorry... this thread is getting long. It's ok w/ my.... I'm just hopeful you won't lose patience!!

Ok, I've now tried Sara's recommendations. Still, something is not working out.

The snapshots include the data sets, so I won't list them again.

1. snapshot "Answer -- Incorrect_1" -- the code executes but produces incorrect result. It should be (3, 1) instead of (2, 1)

2. snapshot "Answer -- Incorrect_2" -- the code executes but produces incorrect result. It should be (8, 6) instead of (1)

3. snapshot "Answer -- Does Not Produce Answer" -- the code throws AccVio error (line #105). See snapshot "AccVio_2"

This is frustrating... I'm just glad I have some help from experts like you (Sara) & sjklein42.

Again, pls find latest code below (Sara's changes only). 'Trying to not mix up recommendations.

Recommendations?

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <math.h> #include <limits.h>using namespace std;#define MAX 10class knapsack{ private : int n, capacity, value[MAX][MAX]; struct object { int weight; int value; } obj[MAX]; public : void getdetails(int &, int &); void initialise(); int mfknapsack(int, int); void display(int);};void knapsack :: getdetails(int &no, int &cap){ int i; cout << "\nEnter the number of objects: "; cin >> n; no = n; cout << "\nEnter the maximum capacity of the Knapsack: "; cin >> capacity; cap = capacity; cout << "\nEnter the Weights and Values of " << n << " objects\n"; for (i = 0; i < n; i++) // Sara's recommendation... change from: for (i = 1; i <= n; i++) { cout << endl; cout << "Weight[" << i << "] = "; cin >> obj[i].weight; cout << "Value[" << i << "] = "; cin >> obj[i].value; }}void knapsack :: initialise(){ int i, j; for (i = 0; i < MAX; i++) // Sara's recommendation... change from: for (i = 0; i <= n; i++) for (j = 0; j < MAX; j++) // Sara's recommendation... change from: for (j = 0; j <= capacity; j++) { if (i == 0 || j == 0) value[i][j] = 0; else value[i][j] = -1; }}int knapsack :: mfknapsack(int r, int c) // Sara's recommendation... change from: int knapsack :: mfknapsack(int n, int c){ int val, temp, temp1; if (value[r][c] < 0) // Sara's recommendation... change from: if (value[n][c] < 0) { temp = mfknapsack(r - 1, c); // Sara's recommendation... change from: if (c < obj[n].weight) if (c < obj[r].weight) // Sara's recommendation... change from: if (c < obj[n].weight) val = temp; else { temp1 = obj[r].value + mfknapsack(r - 1, c - obj[r].weight); // Sara's recommendation... change from: temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight); if (temp1 > temp) val = temp1; else val = temp; } value[r][c] = val; // Sara's recommendation... change from: value[n][c] = val; } return (value[r][c]); // Sara's recommendation... change from: return (value[n][c]);}void knapsack :: display(int cost){ int i, next, cap; cout << "\nThe objects included in the optimal subset are: "; next = n-1; // Sara's recommendation... change from: next = n; cap = capacity-1; // Sara's recommendation... change from: cap = capacity; for (i = n-1; i > 0; i--) // Sara's recommendation... change from: cap = capacity; { if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; } cout << "\n\nThe maximum profit obtained is: "; cout << cost;}int main(){ int profit, no, cap; knapsack k; k.getdetails(no, cap); k.initialise(); profit = k.mfknapsack(no, cap); k.display(profit); system("pause"); return 0;}

Let's focus on your "display" function. I think we made too many changes and messed it up. Here's the original:

void knapsack :: display(int cost){ int i, next, cap; cout << "\nThe objects included in the optimal subset are: "; next = n; cap = capacity; for (i = n; i > 0; i--) { if (value[next][cap] != value[next - 1][cap]) { cout << i << " "; cap -= obj[i].weight; } next = i - 1; } cout << "\n\nThe maximum profit obtained is: "; cout << cost;}

I'll start over from there with this observation.:

It seems like "next" and "i" are always going to be equal. First time through the "for" loop, "next" will be equal to n. "i" is also set to be equal to n. At the end of the loop, both "next" and "i" are decremented, so they are both now equal to n-1. And so on.

Not what you meant, I am sure. Can you explain what you are trying to do with the two variables next and i?

As an aside, I am not sure how this whole algorithm is supposed to work. In plain words, can you tell us what is the "meaning" of the value array? For example, what does the number in value[3][5] mean?

In the knapsack problem don't you need to handle non-integer weights or values? Or just integer weights and values? Even then, what if the total weight is greater than the number of items? Like 5 items but their average weight is 10 so the maximum weight in the knapsack could be as much as 50?

This also raises another point that sara made about field names. You should not give such common names to your fields, like "n" or "value". Save these for local variables. Give meaningful and longer names to field names and it will save you much grief in the future. I even prefix all my field names with letters so I know what structure they belong to, like ks_count instead of n, and ks_capacity instead of cap. I picked ks to stand for knapsack just to keep the names from being too long.

i will look for the algorithm and logic and come back.

Sara

0

ExpExchHelpAuthor Commented:

Thanks for the "persistent" comment... I appreciate it. 8)

Ok, let me go through your latest response:

Your code recommendations (line 1:18). Which baseline (posting id) should I use when inserting this new code?

>> In plain words, can you tell us what is the "meaning" of the value array? For example, what does the number in value[3][5] mean? <<
Basically, I need to add three items into a knapsack that has a maximum weight capacity of five weight units. I actually came a good video on YouTube. I actually took his data set examples since they can be easily verified on a piece of paper.
If you like, skip to time 1:50 in the video. It explains (in much better detail than I could provide in words) what it does. The video can be found at: http://www.youtube.com/watch?v=EH6h7WA7sDw

>> In the knapsack problem don't you need to handle non-integer weights or values? <<
Yes, only integers need to be handled. And, actually, I'd like to include only a "binary integer" solution. I only can pack one of each item. I cannot pack the same items more than once.

>> what if the total weight is greater than the number of items? <<
That would be a constraint violation. Right now, I'll stick w/ the 3 data samples as shown in the snapshots. Again, the easiest one to test (for validity is the one from the video). But then again, that one does NOT blow up on me... ultimately, I'd like to test the data set where a have 10 items and my MAX capacity is 900.

>> This also raises another point that sara made about field names. <<
Fortunately/unfortunately, I found this code online. I'm not taking credit for it... how could I? I'm a novice in C++ and need to learn a lot. That's why some of my answers may have been vague as I'm not fully understanding some of the code's logic. Basically, I'm very flexible on making the necessary code changes.

>> Free advice. Isn't it wonderful? <<
Yes it is!!! But I assure you, I'm not taking it for granted. I'm very much appreciative of the help you've been giving me.

Standing by for more suggestions (... although I'll have to take a break for 2-3 hours). I'll be back online in the early afternoon (Eastern US timezone).

Thanks again!!

EEH

0

ExpExchHelpAuthor Commented:

sarabande:

Thanks, Sara. Is there's a chance that you'd also post the entire code. I'd like to make sure I'm not missing some and spent some of your time (unecessarily) due to mis-communication.

You are on track, but re your suggested change to:

profit = k.mfknapsack(no-1, cap-1);

I thought so too. In fact, we've been down that exact path before (see above 02/20/11 11:11 PM, ID: 34940289). It caused other (worse) problems. At first I thought that would help, but I believe that the two arguments to mfknapsack mean something like (1) the number of items remaining to choose from, and (2) the remaining weight capacity of the knapsack.

0

ExpExchHelpAuthor Commented:

sjklein42, sarabande:

Wow... this thread is getting long. I'm glad you aren't getting upset w/ me.

I certainly want to get this to work, but I realize that this code (I found it somewhere on the web) may not be the best foundation.

Both of you seem to be experts and if you're "challenged" (sorry, this is NOT meant in a negative way) to follow this logic then it would be a "life's mission" for me. 8)

I've come across some other code that seems to work and addresses the 0-1 Greedy algorithm.

If you prefer I could post this code here. However, I want to make sure that I don't upset you given all the effort you've already put in this.

If so, I'd close this posting, award both of you the points... then I'd open another thread ... which would require additional help though.

I watched the video - very interesting - but I agree with sara that it looks like it will be hard to get your code working the way it is now just by tweaking. I agree that starting over fresh is the best approach.

0

ExpExchHelpAuthor Commented:

sjklein42, sarabande:

Ok... great. I will close this thread... and start over w/ the other code which has a more solid baseline.

For instance, I don't have to type in the values... they are declared at the beginning of the program. That in itself will make it easier.

I'll post the baseline shortly and provide you a link.

Both of you have contributed to this thread... I'm not going to count the posts. So, I hope you're ok w/ my splitting the points.

The most important thing (I think) is the recognition for having helped a great deal, right?

0

ExpExchHelpAuthor Commented:

Wow... I applaud the help and patience from the Experts Exchange "gurus" >> sjklein42 << AND >> sarabande <<.

Both of them have helped me a great deal w/ a problem that I'm trying to solve.

In the end, I've provided a foundation (code) that did meet the fundamental criteria for making the required modifications.

Nevertheless, both of them have shown their professionalism -- again demonstrated with good recommendations AND absolute patience!!!

It works with both data sets... 'just need to add the 2nd constraint.

The "Greedy" method is only step 1 out of 2 though... I will have to modify the code with a "Local Search" method. That, however, is a different question in itself.

I'd truly welcome your assistance in this matter. I'm confident that this new set to code will be easier to work with.

EEH

0

ExpExchHelpAuthor Commented:

sjklein42, sarabande:

No, I've not forgotten about this. Fortunately, I've figured out the "Greedy" algorithm. It works great. Now, I'm working on part 2 of 2.... the implementation of a "Local Search" algorithm.

I've opened another question with -- I think -- a good background on what I'm trying to achieve. If you're interested, I welcome you to have a look at:

U is the set of objects objects with w(eight) and v(alue) property

B is the capacity (integer only)

Input: U, B, w, v

R := [1…(n+1), 0…B]-Matrix all cells initially 0

FOR i = n … 1

FOR j = 1 … B

IF w(i) <= j

R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )

ELSE

R[i,j] := R[i+1,j]

Output: R[1,B]

you see matrix R has dimensions n+1, B what explains the out-of-boundary access when the matrix has only MAX x MAX dimensions.

you see outer loop starts with row n (== index n-1) (what is equivalent to initial call of mfknapsack(no-1, cap-1)) and goes backwards until 1 (index 0).

the final (best) result is in R[1, B] what is row number 0 and column cap-1 but it needs some kind of backtracking to actually determine which objects have been included to the optimum (must not be unique).

i am not quite sure whether it is easier to write the code newly from that algorithm or try to correct the current code which unfortunately has some basic lacks in dimensioning and accessing of rows and columns.

Sara