Solved

C++ Error "Access Violation"

Posted on 2011-02-20
47
1,056 Views
Last Modified: 2012-05-11
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 10

class 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;
}

Open in new window

DataEntry-2-Sets.xls
0
Comment
Question by:ExpExchHelp
  • 28
  • 15
  • 4
47 Comments
 
LVL 16

Expert Comment

by:sjklein42
ID: 34939441
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
 

Author Comment

by:ExpExchHelp
ID: 34939487
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
 
LVL 16

Expert Comment

by:sjklein42
ID: 34939510
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;
	}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34939518
sjklein42:

Please see previous response.   I changed line 36 as you suggested to >> for (i = 0; i <= n; i++) <<

Now, however, when entering "3", I actually prompted to enter four data sets.

Also, when entering "10" (11 data sets), I still end up getting the same access violation error.

Again, given my novice status, I'd welcome any feedback for eliminating the error so that I can enter 10 data sets.

'Much obliged!!

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34939532
Ok... I just posted my response while you already provided some feedback.

I made the changed >> obj[i-1] << a moment ago.   I'm back to adding only 3 records.

However, for data set #1, the solution has changed from objects "3  1" to "2   1".

That in itself would be an issue.   The access problem remains for 10 data sets as well.

Again, I appreciate your help!!
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34939557
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.

cout << "debugging n = " << n;
if (c < obj[n].weight)
...

Open in new window

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
 

Author Comment

by:ExpExchHelp
ID: 34939706
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.

EEH


Snapshot.jpg
0
 

Author Comment

by:ExpExchHelp
ID: 34939713
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?

EEH
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34939782
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
 

Author Comment

by:ExpExchHelp
ID: 34939876
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
 

Author Comment

by:ExpExchHelp
ID: 34939894
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?

EEH
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940002
Let's consider the case where you have 10 items.

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 think you mean to use n-1 on line 104

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

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34940091
sjklein42:

Now that you point this out, it makes sense.

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.

Do you know what wrong w/ that line?

EEH
Error.jpg
0
 

Author Comment

by:ExpExchHelp
ID: 34940112
Please see previous post... pointing to linen #88.

Another piece of information (not sure if it's useful) is the info as shown in the snapshot.

Does that help to trouble-shoot?

EEH
MoreInfo.jpg
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940115
You also have another class of bug.

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;
		}
}

Open in new window

0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940133
When looping backwards do it this way:

Line 86:

	for (i = n-1; i >= 0; i--)

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34940233
sjklein42:

Slowly but surely... "we" are getting there.   8)

Ok, the error in line 88 disappeared.   Yeah!!!

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".

Do you recommend leaving it as follows?

Screenshot is attached.


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

Open in new window

Error-withLargeNumbers.jpg
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940289
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.
 
 profit = k.mfknapsack(no-1, cap-1); 

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34940327
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.

Thoughts/recommendations?

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34940328
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.

Thoughts/recommendations?

EEH
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940359
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
 

Author Comment

by:ExpExchHelp
ID: 34940371
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 10


class 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;
}

Open in new window

OutputWithSmallValues.jpg
dbbhook.c
0
 

Author Comment

by:ExpExchHelp
ID: 34940400
I just saw your other posting.

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
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 

Author Comment

by:ExpExchHelp
ID: 34940402
Made an error in the last value...
should be >> - Values for [10]:   400, 575 <<
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940516
I marked a bunch of changes with >>>>>

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;
	}

Open in new window


See the changes below marked with >>>>>:

// 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


class 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;
}

Open in new window

0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940519
Please post the latest code each time you have questions so we don't lose time.
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34940602
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 50



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

Open in new window

0
 
LVL 32

Expert Comment

by:sarabande
ID: 34941657
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
 

Author Comment

by:ExpExchHelp
ID: 34942321
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:

My posting -- http://34940371     ?

or

sjklein42's posting -- http://34940516     ?






0
 

Author Comment

by:ExpExchHelp
ID: 34942392
sjklein42:

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 10


class 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;
}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34942402
Again, pls refer to previous posting.  

Sorry for the wrong hyperlinks... it should have been http:#34940516.
0
 

Author Comment

by:ExpExchHelp
ID: 34942466
sjklein42:

I made the code changes per http://#34940602

Still get an error.   See snapshots below:


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)?


// 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 recommendation


class 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;
}

Open in new window

MaxCap.jpg
AccVio.jpg
0
 

Author Comment

by:ExpExchHelp
ID: 34942490
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
 

Author Comment

by:ExpExchHelp
ID: 34942628
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 10


class 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;
}

Open in new window

Answer----Incorrect-1.jpg
Answer----Incorrect-2.jpg
Answer----Does-Not-Produce-Answe.jpg
AccVio-2.jpg
0
 
LVL 32

Expert Comment

by:sarabande
ID: 34942654
yes, my comment was based on your last code before my comment in posting http:#34940371.  

Sara
0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34942678
ExpExchHelp,

You are persistent if nothing else.  Good for you.

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;
}

Open in new window


 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.


Free advice.  Isn't it wonderful?

;)
0
 
LVL 32

Expert Comment

by:sarabande
ID: 34942705
the access violation is because

      if (value[r][c] < 0)

which are out of boundary when calling

   profit = k.mfknapsack(no, cap);

from main with 10/10

you could try

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

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

Sara

0
 

Author Comment

by:ExpExchHelp
ID: 34942805
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
 

Author Comment

by:ExpExchHelp
ID: 34942820
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.

Much obliged!!

EEH

0
 
LVL 16

Expert Comment

by:sjklein42
ID: 34942844

   sarabande:,

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
 
LVL 32

Accepted Solution

by:
sarabande earned 250 total points
ID: 34945669
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.

Sara


0
 

Author Comment

by:ExpExchHelp
ID: 34945947
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.

Let me know which route you'd like to go.

EEH
0
 
LVL 16

Assisted Solution

by:sjklein42
sjklein42 earned 250 total points
ID: 34945999
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
 

Author Comment

by:ExpExchHelp
ID: 34946055
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
 

Author Closing Comment

by:ExpExchHelp
ID: 34946097
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!!!

You guys "rock"!!!

Again, thanks!

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34946297
sjklein42, sarabande:

The new "foundation" code has been posted at:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_26837161.html

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
 

Author Comment

by:ExpExchHelp
ID: 34957851
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:

http://www.experts-exchange.com/Programming/Languages/CPP/Q_26840869.html

Again, just wanted to close the loop w/ you given that you've provided outstanding help on the "greedy" method.  
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

We all know that functional code is the leg that any good program stands on when it comes right down to it, however, if your program lacks a good user interface your product may not have the appeal needed to keep your customers happy. This issue can…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now