Solved

C++ -- Adding a Constraint

Posted on 2011-02-20
56
1,188 Views
Last Modified: 2012-05-11
I'm working on a developing a program that meets the "0-1 Knapsack" concept.    See URL below for more conceptual details:
http://en.wikipedia.org/wiki/Knapsack_problem

Right now, I've developed the basic framework (I googled for existing code and tried to modify it).

At this point, the code below somewhat works.    By "somewhat", I mean that it doesn't meet the "0-1 Knapsack" concept.    Essentially, the program adds four items of #3 (based on its greatest value contribution)... and then adds #1 due to the remaining (unfilled) weight capacity.

So, while the code does determine the greatest value contribution, I want to modify it so that I only can add one item at the most to the knapsack.

Does anyone know how to add this constraint (i.e, once an added has been selected for the knapsack, remove it from the array so that I can't be selected again)?

Thx,
EEH

P.S.   Also, as this is not my original code, I'm having a tough time understanding the ForLoop and WhileLoop.   If anyone could "walk me through" this (by adding a few comments), it would greatly help me in the continuation of the program development.    Again, thanks!!!

P.S.S.   If you think that this code is too cumbersome and could work better using a different method, I"m open to recommendations.  
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>                                                                                    
#include <limits.h>
using namespace std;

int linecount = 10;															    // The number of objects 
#define MAXWEIGHT 900
int knapSack_Max_Weight = 900;

int knapSack_Max_Volume = 800;
														
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's itemValue
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's itemVolume
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's itemWeight

// Declarations of independent functions
void knapsackGreedy();


int main()
{		
	// Function call
	knapsackGreedy();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}


void knapsackGreedy() {
	int a[MAXWEIGHT];						// a[i] holds the maximum itemValue that can be obtained using at most i itemWeight 
	int lastAddedItem[MAXWEIGHT];			// Calculate which objects were added
	int i, j;
	int aux;

	for (i=0; i<=knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i=1; i<=knapSack_Max_Weight; ++i)
		for (j=0; j<linecount; ++j)
			if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
				a[i] = a[i - itemWeight[j]] + itemValue[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
        aux -= itemWeight[lastAddedItem[aux]];
	}

	cout << endl << endl;
	cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
}

Open in new window

0
Comment
Question by:ExpExchHelp
  • 32
  • 20
56 Comments
 
LVL 10

Expert Comment

by:cdebel
ID: 34938517
According to Wikipedia article, Greedy approximation algorithm is not the best method for 0-1.  You could probably add some conditions to add 1 item of each maximum, but it wouldn't be optimal.

I've already coded C++ years ago, but actually the language is not the problem.  I'll read a bit about the knapsack to find a way to compute that.
0
 

Author Comment

by:ExpExchHelp
ID: 34938919
cdebel:

Thanks... 'much obliged.

And, yes, you're right, "Greedy" won't give the optimal solution.    This however is only step 1 out of two steps.   I can/will have to improve the Greedy algorithm with a "Local Search" method.    That's a different problem though.

For right now, I'll be happy if I can get the "Greedy" algorithm to work... or modify the existing code by adding the constraint.

Again, thousand thanks in advance.

EEH
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34944238
Sorry for the delay.

I've tried to think about the best way to solve this problem, and i don't see any better solution than checking every possibles combinations.  There's probably some algorythm for that, but i've not found any.

This method is good because it help you to find the best value for your knapsack, but more you will have objects to pick-up, more it will take time.   Actually for 10 items, it's really fast.   But if you would get 30 items, i would think about using a Greedy method instead of this one.

 
// Required C++ libraries and header files
#include <iostream>;
#include <math.h>;

using namespace std;

#define MAXWEIGHT 900

int linecount = 10;															    // The number of objects 
int knapSack_Max_Weight = 900;													
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's itemValue
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's itemWeight

// Declarations of independent functions
void knapsackGreedy();
void knapsack01();

typedef struct PossibleMatch {
	int nItem;
	int nValue;
	int nWeight;
}  ;

void knapsack01() {
	// This method is doing a brutal check for the best match for a knapsack 0-1 by testing every possible method
	int nBit;
	int i;
	PossibleMatch BestMatch;
	PossibleMatch MyItem;

	BestMatch.nValue =  0;
	BestMatch.nWeight = 0;
	BestMatch.nItem = 0;
	for (i=1; i <= (int)pow(2.0, linecount); i++)
	{
		MyItem.nValue = 0;
		MyItem.nWeight = 0;
		for (nBit = 0; nBit <= linecount; nBit++)
		{
			if (i & (int)pow(2.0, nBit))
			{
				MyItem.nValue += itemValue[nBit];
				MyItem.nWeight += itemWeight[nBit];
			}
		}

		if ((MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nValue > BestMatch.nValue)) {
			BestMatch.nItem = i;
			BestMatch.nValue = MyItem.nValue;
			BestMatch.nWeight = MyItem.nWeight;
		}
	}

	// Display the best result
	for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
	{
		if (BestMatch.nItem & (int)pow(2.0,nBit)) {
			std::cout << "Added item #" << (nBit+1) << std::endl;
		}
	}
}

void knapsackGreedy() {
	int a[MAXWEIGHT];						// a[i] holds the maximum itemValue that can be obtained using at most i itemWeight 
	int lastAddedItem[MAXWEIGHT];			// Calculate which objects were added
	int i, j;
	int aux;

	for (i=0; i<=knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i=1; i<=knapSack_Max_Weight; ++i)
		for (j=0; j<linecount; ++j)
			if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
				a[i] = a[i - itemWeight[j]] + itemValue[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
        aux -= itemWeight[lastAddedItem[aux]];
	}

	cout << endl << endl;
	cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
};


int main()
{		
	// Function call
	knapsack01();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}

Open in new window

0
 
LVL 10

Expert Comment

by:cdebel
ID: 34945516
If you really want to use a Greedy method, but using having only 1 item of each maximum, then you could use this method...

 
void knapsackGreedy01() {
	int SortedRatios[10];
	float Ratios[10];
	float tmp1;
	int weightLeft = MAXWEIGHT;
	int i, j;

	// Calculate the ratios
	for (i=0; i < 10; i++) {
		Ratios[i] = (float)itemValue[i] / itemWeight[i];
		SortedRatios[i] = i;
	}

	// Sort them
	for (i=0; i < linecount; i++)
		for (j=i; j < linecount; j++) {
			if (Ratios[i] < Ratios[j]) {
				// Swap ratios
				tmp1 = Ratios[i];
				Ratios[i] = Ratios[j];
				Ratios[j] = tmp1;

				tmp1 = SortedRatios[i];
				SortedRatios[i] = SortedRatios[j];
				SortedRatios[j] = tmp1;
			}
		}

	// Get the best values, by choosing unique items
	i = 0;
	while (weightLeft > 0) {
		if (weightLeft - itemWeight[SortedRatios[i]] >= 0) {
			weightLeft -= itemWeight[SortedRatios[i]];
			std::cout << "Added item #" << SortedRatios[i++] + 1 << std::endl;
		}
		else {
			break;
		}

	}
}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34945858
cdebel:

Wow... you're truly a "guru".    I really really appreciate your expertise on this subject.    Ok, I've tested both solution with three data sets.    All of them give me the expected output.... YEAH!!!!   8)

When compiling, I noticed several warnings.   These are:
warning C4067: unexpected tokens following preprocessor directive - expected a newline
warning C4067: unexpected tokens following preprocessor directive - expected a newline
warning C4091: 'typedef ' : ignored on left of 'PossibleMatch' when no variable is declared
warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
warning C4244: '=' : conversion from 'float' to 'int', possible loss of data

Should I simply ignore them?  

Btw, I just realized that I forgot to mention one element in the original posting.   I TRULY HOPE THIS WON'T CAUSE YOU MAJOR FRUSTRATION WITH ME.

Essentially, the code that I had found included the items "values" and "weights", where the sum of the items' weights could not exceed the knapsack's capacity.    There's a second constraint that I would like to include.    This could covers "volume".

The approach is identical to weight the weight concept.   I cannot exceed the max volume.  

So, again, instead just keeping weight in mind, I would like to keep "weight AND volume" in mind.  
The values for all three are:

Value:
150, 250, 450, 150, 50, 350, 175, 275, 275, 575

Volume:
100, 200, 200, 200, 200, 200, 200, 200, 400, 400

Weight:
100, 200, 200, 200, 200, 200, 200, 200, 300, 300

... where Max Volume = 800 volume units and Max Weight = 900 weight units

Can the second constraint (volume) be tied in this code?   If yes how?

For right now, this is the next step that I'd like to achieve.    However, allow me to also mentioned another piece of information.    See below "break".


BREAK

Now, to your questions.   I completely appreciate your point on optimization (i.e., processing speed).   Based on your assessment, which one would you recommend (solution #1 or #2).    

Well, maybe the following will help getting before you answer this question.    As mentioned in posting http:#34938919, the "Greedy" method is step 1 out of 2.

Again, it seems that either approach addresses step 1.   Now to step 2.... I'd like include a "Local Search" algorithm.    What does that mean?    Well, I could provide a major rewrite on this, but the basics are covered at:   http://en.wikipedia.org/wiki/Local_search_%28constraint_satisfaction%29

Essentially, my "Greedy" gives me (potentially) in near to optimal solution.    Forget for a moment that I know what the optimal solution is (based on having used your Excel solution a few days ago).  

The Local Search will take the Greedy's method and gradually "attempt" to improve it.    This could be done by swapping items' in and out.  

But again, unless the "Local Search" should be considered in this development stage right now, adding the "volume constraint" is more important to me at this moment.

Btw, I truly appreciate your help (again).    Your expertise and patience make this forum truly the best place on the web.

Thousand thanks in advance!!!

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34946568
cdebel:

Please see my previous posting first.

In respect to the 2nd constraint (volume), I've taken a stab at it.   It seemed straight-forward until I hit the function << knapsackGreedy01 <<.   More specifically, I wasn't sure how to include it into the "ratio" calculation.

Thoughts/recommendations for this step (thus far)?

EEH


// Required C++ libraries and header files
#include <iostream>
#include <math.h>

using namespace std;


// DATA SET #1:
//#define MAXWEIGHT 5
//#define MAXVOLUME 6																// NOT YET IMPLEMENTED!!!
//
//int linecount = 3;																// The number of objects 
//int knapSack_Max_Weight = 5;													// Max weight
//int knapSack_Max_Volume = 6;													// Max volume          -- NOT YET IMPLEMENTED!!!
//int itemValue[3]  = {5, 3, 4};													// Item's itemValue
//int itemWeight[3] = {2, 4, 3};													// Item's itemWeight
//int itemVolume[3] = {2, 3, 2};													// Item's itemVolume   --  NOT YET IMPLEMENTED!!!


// DATA SET #2:
#define MAXWEIGHT 800
#define MAXVOLUME 900															// NOT YET IMPLEMENTED!!!

int linecount = 10;																// The number of objects 
int knapSack_Max_Weight = 800;													// Max weight
int knapSack_Max_Volume = 900;													// Max volume
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's itemValue
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's itemWeight
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's itemVolume   --  NOT YET IMPLEMENTED!!!



// Declarations of independent functions
void knapsackGreedy();
void knapsack01();

typedef struct PossibleMatch {
	int nItem;
	int nValue;
	int nWeight;
	int nVolume;
};  

void knapsack01() {
	// This method is doing a brutal check for the best match for a knapsack 0-1 by testing every possible method
	int nBit;
	int i;
	PossibleMatch BestMatch;
	PossibleMatch MyItem;

	BestMatch.nValue =  0;
	BestMatch.nWeight = 0;
	BestMatch.nVolume = 0;
	BestMatch.nItem = 0;
	for (i=1; i <= (int)pow(2.0, linecount); i++)
	{
		MyItem.nValue = 0;
		MyItem.nWeight = 0;
		MyItem.nVolume = 0;
		for (nBit = 0; nBit <= linecount; nBit++)
		{
			if (i & (int)pow(2.0, nBit))
			{
				MyItem.nValue += itemValue[nBit];
				MyItem.nWeight += itemWeight[nBit];
				MyItem.nVolume += itemVolume[nBit];
			}
		}

		if ((MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nVolume <= knapSack_Max_Volume) && (MyItem.nValue > BestMatch.nValue)) {
			BestMatch.nItem = i;
			BestMatch.nValue = MyItem.nValue;
			BestMatch.nWeight = MyItem.nWeight;
			BestMatch.nVolume = MyItem.nVolume;
		}
	}

	// Display the best result
	for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
	{
		if (BestMatch.nItem & (int)pow(2.0,nBit)) {
			std::cout << "Added item #" << (nBit+1) << std::endl;
		}
	}
}

void knapsackGreedy01() {
	int SortedRatios[10];
	float Ratios[10];
	float tmp1;
	int weightLeft = MAXWEIGHT;
	int volumeLeft = MAXVOLUME;
	int i, j;

	// Calculate the ratios
	for (i=0; i < 10; i++) {
		Ratios[i] = (float)itemValue[i] / itemWeight[i];
		SortedRatios[i] = i;
	}

	// Sort them
	for (i=0; i < linecount; i++)
		for (j=i; j < linecount; j++) {
			if (Ratios[i] < Ratios[j]) {
				// Swap ratios
				tmp1 = Ratios[i];
				Ratios[i] = Ratios[j];
				Ratios[j] = tmp1;

				tmp1 = SortedRatios[i];
				SortedRatios[i] = SortedRatios[j];
				SortedRatios[j] = tmp1;
			}
		}

	// Get the best values, by choosing unique items
	i = 0;
	while (weightLeft > 0) {
		if (weightLeft - itemWeight[SortedRatios[i]] >= 0) {
			weightLeft -= itemWeight[SortedRatios[i]];
			std::cout << "Added item #" << SortedRatios[i++] + 1 << std::endl;
		}
		else {
			break;
		}
	}

}


int main()
{		
	// Function call
	knapsack01();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}

Open in new window

0
 
LVL 10

Expert Comment

by:cdebel
ID: 34946573
About your concerns with warnings, you could ignore them.  If they bug you, they are easy to solve by clicking on them.   I'm using VS2010 and it doesn't produce any warning at the moment with this code.

ex: "possible loss of data" is caused by a float temporary variable (tmp1) assigned to an int variable.  It doesn't cause any loss because i know that what is inside tmp1 at this moment is really an Integer.

---

As i've mentionned, if you use small amounts of items, solution knapsack01 is the best since it give you the best value for your knapsack.  If you have a lot of items, i would choose solution knapsackGreedy01 because it's way faster. (but it might have a slightly better match)

----

Don't worry for the question for volume, i'm not bugged by that.  But keep in mind that other people might help you better if you ask a new question.

So here is how i would do it to implement the volume.  I've implemented it in both solutions, but i don't really know if it's efficient in knapsackGreedy01 since i don't do any ratio based on volume.  And i guess that the best ratio would be a combination of volume+weight, not only weight.  But knapsack01 as usual give the optimal value per volume/weight.

 
// Required C++ libraries and header files
#include <iostream>;
#include <math.h>;

using namespace std;

#define MAXWEIGHT 900
#define MAXVOLUME 800

int linecount = 10;															    // The number of objects 
int knapSack_Max_Weight = 900;													
int knapSack_Max_Volume = 800;
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's Value
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's Weight
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's Volume

// Declarations of independent functions
void knapsackGreedy();
void knapsackGreedy01();
void knapsack01();

typedef struct PossibleMatch {
	int nItem;
	int nValue;
	int nWeight;
	int nVolume;
}  ;

void knapsack01() {
	// This method is doing a brutal check for the best match for a knapsack 0-1 by testing every possible method
	int nBit;
	int i;
	PossibleMatch BestMatch;
	PossibleMatch MyItem;

	BestMatch.nValue =  0;
	BestMatch.nWeight = 0;
	BestMatch.nVolume = 0;
	BestMatch.nItem = 0;
	for (i=1; i <= (int)pow(2.0, linecount); i++)
	{
		MyItem.nValue = 0;
		MyItem.nWeight = 0;
		MyItem.nVolume = 0;
		for (nBit = 0; nBit <= linecount; nBit++)
		{
			if (i & (int)pow(2.0, nBit))
			{
				MyItem.nValue += itemValue[nBit];
				MyItem.nWeight += itemWeight[nBit];
				MyItem.nVolume += itemVolume[nBit];
			}
		}

		if ((MyItem.nVolume <= knapSack_Max_Volume) && (MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nValue > BestMatch.nValue)) {
			BestMatch.nItem = i;
			BestMatch.nValue = MyItem.nValue;
			BestMatch.nWeight = MyItem.nWeight;
			BestMatch.nVolume = MyItem.nVolume;
		}
	}

	// Display the best result
	for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
	{
		if (BestMatch.nItem & (int)pow(2.0,nBit)) {
			std::cout << "Added item #" << (nBit+1) << std::endl;
		}
	}
}

void knapsackGreedy01() {
	int SortedRatios[10];
	float Ratios[10];
	float tmp1;
	int weightLeft = MAXWEIGHT;
	int volLeft = MAXVOLUME;
	int i, j;

	// Calculate the ratios
	for (i=0; i < 10; i++) {
		Ratios[i] = (float)itemValue[i] / itemWeight[i];
		SortedRatios[i] = i;
	}

	// Sort them
	for (i=0; i < linecount; i++)
		for (j=i; j < linecount; j++) {
			if (Ratios[i] < Ratios[j]) {
				// Swap ratios
				tmp1 = Ratios[i];
				Ratios[i] = Ratios[j];
				Ratios[j] = tmp1;

				tmp1 = SortedRatios[i];
				SortedRatios[i] = SortedRatios[j];
				SortedRatios[j] = tmp1;
			}
		}

	// Get the best values, by choosing unique items
	i = 0;
	while (weightLeft > 0) {
		if ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volLeft - itemVolume[SortedRatios[i]] >= 0)) {
			weightLeft -= itemWeight[SortedRatios[i]];
			volLeft -= itemVolume[SortedRatios[i]];
			std::cout << "Added item #" << SortedRatios[i++] + 1 << std::endl;
		}
		else {
			break;
		}

	}
}


void knapsackGreedy() {
	int a[MAXWEIGHT];						// a[i] holds the maximum itemValue that can be obtained using at most i itemWeight 
	int lastAddedItem[MAXWEIGHT];			// Calculate which objects were added
	int i, j;
	int aux;

	for (i=0; i<=knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i=1; i<=knapSack_Max_Weight; ++i)
		for (j=0; j<linecount; ++j)
			if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
				a[i] = a[i - itemWeight[j]] + itemValue[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
        aux -= itemWeight[lastAddedItem[aux]];
	}

	cout << endl << endl;
	cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
};


int main()
{		
	// Function call
	knapsack01();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}

Open in new window


---

About your local search, it would probably take some time... i don't have that time for the moment.   You should ask another question to get some help
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34946634
I see that we got the same idea for the knapsack01, and the same problem in the greedy01 version.

I've no clue how to check for that in that algorithm.  For the moment, my version only make sure that you don't go over the limit of volume, but the final solution might not be optimal.  Greedy algorithm is an approximation anyway.   There might be a way to combine 2 ratios together but which one would have more importance?
0
 

Author Comment

by:ExpExchHelp
ID: 34947068
cdebel:

Again, thousand thanks for your help!!!   It is much appreciated.

Quick follow-up question about the program.   Currently, it's calling

void knapsackGreedy();
void knapsackGreedy01();

Given that I'm only dealing w/ a small data set right now, are they duplicative?    Shall I remove one... or do the Greedy and Greedy01 depend on each other?

Also, final question... is there's a chance for you to include to very basic/quick comments (not every line) but for the major functions/computations.    

That'll allow me to study your logic and make better sense of it.

Thousand thanks in advance!

EEH

0
 
LVL 10

Expert Comment

by:cdebel
ID: 34947157
knapsackGreedy01 = knapsack01.  Both are solving the 0-1 problem of the knapsack.

knapsackGreedy is used to solve the Unbounded knapsack problem. (so this version will give a result with many time the same item and few others to fill up the pack).

So both are addressing different problem, therefore both should be kept.  To choose between knapsackGreedy01 and knapsack01, you could check how many items you got, and if you have more than 20 items for example, then you would use knapsackGreedy01.

I'll add some comments and come back in few minutes

0
 

Author Comment

by:ExpExchHelp
ID: 34947169
cdebel:

Sorry... one more follow-up question...

If I wanted to also display/print out the respective values, weights, and volumes, but the "Total Value", how would I go about it.

I'll dabble w/ this but I just wanted to make sure I still "catch you" before you lose track of this.

Thank you,
EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34947178
cdebel:

'Just saw your posting... man, you are truly awesome!!!!

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34947238
cdebel:

Wow... I just realized that your algorithm (based on this data set) actually hits the optimal solution.

As you stated >> ".... the final solution might not be optimal" <<, the Greedy method provides only an approximate solution.    It is the Local Search that might improve it via small iterations.

However, I just compared the output of your Greedy01 solution with the one in Excel.    Both produce (1, 3, 6, 10) as the optimal solution.

So, somewhere in your code, you actually solved the "Local Search".... TOTALLY COOL!!!

Hopefully I can see from your comments which lines of code might fall into the "greedy" or "local search" category.

Again, I'm thrilled about the help you provided me.

EEH
0
 
LVL 10

Accepted Solution

by:
cdebel earned 500 total points
ID: 34947451
Yes, the Local Search problem is solved by knapsack01.  But if you choose another method, like an unbounded method, you will have to figure out how to do it, or just use a knapsack01 similar method (it would require to use an array of Int instead of a simple Int (because you got to store values, not only 0 or 1).  

I've commented everything, except the function that you already provided because i don't really understand this method.  I've added code to display the weight/volume/value of each items added to the sack, and give a summary once it's completed

 
// Required C++ libraries and header files
#include <iostream>;
#include <math.h>;

using namespace std;

#define MAXWEIGHT 900
#define MAXVOLUME 800

int linecount = 10;															    // The number of objects 
int knapSack_Max_Weight = 900;													
int knapSack_Max_Volume = 800;
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's Value
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's Volume
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's Weight



// Declarations of independent functions
void knapsackGreedy();
void knapsackGreedy01();
void knapsack01();

// Structure used with knapsack01
typedef struct PossibleMatch {
	int nItem;
	int nValue;
	int nWeight;
	int nVolume;
}  ;

void knapsack01() {
	// This function will check for EVERY possible combination, and will keep the best value at the end.
	// There's no logic for ratio "value/weight", therefore it's slower and is more suitable when the number
	// of items are limited.  When having a lot of items, it would be better to use knapsackGreedy01.
	//
	// It use an integer as a binary array since you can add an item only once to the sack.
	int nBit;
	int i;
	PossibleMatch BestMatch;
	PossibleMatch MyItem;

	BestMatch.nValue =  0;
	BestMatch.nWeight = 0;
	BestMatch.nVolume = 0;
	BestMatch.nItem = 0;

	// Loop from 1 to the highest value generated by "x bits".  If you got 10 items, then you got to use 10 bits.   So you have 2^10 possibilities (1024 possibilities).
	for (i=1; i <= (int)pow(2.0, linecount); i++)
	{
		// Reset the current item
		MyItem.nValue = 0;
		MyItem.nWeight = 0;
		MyItem.nVolume = 0;

		// Calculate the value, weight and volume based on the actual possibility
		for (nBit = 0; nBit <= linecount; nBit++)
		{
			// Check if the bit is at 1 in this possibility:
			if (i & (int)pow(2.0, nBit))
			{
				// The bit is ON so it mean that the item need to be inserted
				MyItem.nValue += itemValue[nBit];
				MyItem.nWeight += itemWeight[nBit];
				MyItem.nVolume += itemVolume[nBit];
			}
		}

		// After adding all these items to the sack, we need to check if we exceed the Weight & Volume.  
		// If we don't exceed it, we must check if it's value is higher than the best we have seen so far...
		if ((MyItem.nVolume <= knapSack_Max_Volume) && (MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nValue > BestMatch.nValue)) {
			// This possibility (combination) is better.  So we memorize it, and it's total Value/Weight/Volume to display the best result
			BestMatch.nItem = i;
			BestMatch.nValue = MyItem.nValue;
			BestMatch.nWeight = MyItem.nWeight;
			BestMatch.nVolume = MyItem.nVolume;
		}
	}

	// Display the best result, by checking which bits are ON in that combination.
	for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
	{
		if (BestMatch.nItem & (int)pow(2.0,nBit)) {
			std::cout << "Added item #" << (nBit+1) << "  Weight: " << itemWeight[nBit] << ", Volume: " << itemVolume[nBit] << ", Value: " << itemValue[nBit] << std::endl;
		}
	}
	std::cout << "Total Weight: " << BestMatch.nWeight << std::endl;
	std::cout << "Total Volume: " << BestMatch.nVolume << std::endl;
	std::cout << "Total Value: " << BestMatch.nValue << std::endl;
}

void knapsackGreedy01() {
	// This function will create a knapsack using a greedy method:  That mean that it build a 
	// table of ratios "Value/Weight", then it sort it in descending order to have the highest
	// ratio on top.  Once it's done, it add 1 item of each until there's no more space for 
	// the next item.
	//
	// It might leave the knapsack with some free space and nothing else to fill up because every other
	// items weight are too high.  Therefore, this method is not optimal and could benefit from Local Search
	// function.
	//
	// Since this method is really fast, it can be used with a huge number of items.
	int SortedRatios[10];		// Index of ratios
	float Ratios[10];			// Ratios themselves
	float tmp1;					
	int weightLeft = MAXWEIGHT;
	int volLeft = MAXVOLUME;
	int totalValue = 0;
	int i, j;

	// Calculate the ratios for each items
	for (i=0; i < 10; i++) {
		Ratios[i] = (float)itemValue[i] / itemWeight[i];
		SortedRatios[i] = i;
	}

	// Sort them using a Bubble Sort (check for wiki for more details)
	for (i=0; i < linecount; i++)
		for (j=i; j < linecount; j++) {
			if (Ratios[i] < Ratios[j]) {
				// Swap ratios
				tmp1 = Ratios[i];
				Ratios[i] = Ratios[j];
				Ratios[j] = tmp1;

				tmp1 = SortedRatios[i];
				SortedRatios[i] = SortedRatios[j];
				SortedRatios[j] = tmp1;
			}
		}

	// Adding items with the best value/weight ratio first, and add others until we reach the weight limit.
	// Display each item as soon as we add them to the sack.
	i = 0;
	while (weightLeft > 0) {
		// We make sure that the next combination won't make us go over the Volume & Weight limits that we have fixed
		if ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volLeft - itemVolume[SortedRatios[i]] >= 0)) {
			// We are not going to reach the limit, so we add the item in the sack
			weightLeft -= itemWeight[SortedRatios[i]];
			volLeft -= itemVolume[SortedRatios[i]];			
			std::cout << "Added item #" << SortedRatios[i] + 1 << "  Weight: " << itemWeight[ SortedRatios[i]] << ", Volume: " << itemVolume[ SortedRatios[i]] << ", Value: " << itemValue[ SortedRatios[i]] << std::endl;
			totalValue += itemValue[ SortedRatios[i]];
			i++;
		}
		else {
			break;
		}
	}
	std::cout << "Total Weight: " << knapSack_Max_Weight - weightLeft << std::endl;
	std::cout << "Total Volume: " << knapSack_Max_Volume - volLeft << std::endl;
	std::cout << "Total Value: " << totalValue << std::endl;

}


void knapsackGreedy() {
	int a[MAXWEIGHT];						// a[i] holds the maximum itemValue that can be obtained using at most i itemWeight 
	int lastAddedItem[MAXWEIGHT];			// Calculate which objects were added
	int i, j;
	int aux;

	for (i=0; i<=knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i=1; i<=knapSack_Max_Weight; ++i)
		for (j=0; j<linecount; ++j)
			if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
				a[i] = a[i - itemWeight[j]] + itemValue[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
        aux -= itemWeight[lastAddedItem[aux]];
	}

	cout << endl << endl;
	cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
};


int main()
{		
	// Function call
	knapsackGreedy01();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34947509
cdebel:

Wow... this is awesome.... I can't thank you enough for your help!!!!!

I'm going to study the code and play with other data sets (as well as compare them to Excel's solution.

Final question... how come the sorting order changed from (1, 3, 6, 10) to (3, 6, 1, 10).    'Just curious.

EEH
0
 

Author Closing Comment

by:ExpExchHelp
ID: 34947517
cdebel provided EXCELLENT HELP in this question.

I truly appreciate the support and patience that was provided to me.  

This makes the EE forum truly the best place on the web!!!
0
 

Author Comment

by:ExpExchHelp
ID: 34947703
cdebel:

The last/final question may have gotten "lost" to the other comment.

How come the sorting order changed from (1, 3, 6, 10) to (3, 6, 1, 10).    'Just curious.

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34947946
Oh my... hopefully I didn't cheer too prematurely.

I know you're busy... but I just wanted to share w/ you that I didn't get the optimal solution with another data set (using 13 arbitrary records).

See attached snapshots (console and XLS view).  

Sounds like the "Local Search" is required to gradually improve the outcome.    I'm just confused as to why the 10 original records game the the optimal solution (verified by Excel)... but an additional 3 records makes it not even come close.

Thoughts/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 MAXVOLUME 800
//int knapSack_Max_Volume = 800;
//
//#define MAXWEIGHT 900
//int knapSack_Max_Weight = 900;	
//									
//int linecount = 10;															// The number of objects
//int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};		// Item's Value
//int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's Volume
//int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's Weight




#define MAXVOLUME 1100
int knapSack_Max_Volume = 1100;

#define MAXWEIGHT 1400
int knapSack_Max_Weight = 1400;	
									
int linecount = 13;																			// The number of objects
int itemValue[13]  = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50};		// Item's Value
int itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200};		// Item's Volume
int itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200};		// Item's Weight





// Declarations of independent functions
void knapsack_Greedy_LocalSearch();


// Structure used with knapsack
typedef struct PossibleMatch {
	int nItem;
	int nValue;
	int nVolume;
	int nWeight;
}  ;


// Main() is the programs' "entry point"
int main()
{		
	// Function call
	knapsack_Greedy_LocalSearch();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}


void knapsack_Greedy_LocalSearch() {
	// This function will check for EVERY possible combination, and will keep the best value at the end.
	// There is no logic for ratio "value/weight", therefore it's slower and is more suitable when the number
	// of items are limited.  
	// This solution uses an integer as a binary array since it can add an item only once to the sack.
	//
	// It might leave the knapsack with some free space and nothing else to fill up because every other
	// items weight are too high.  Therefore, this method is not optimal and could benefit from Local Search
	// function.
	//
	// Since this method is really fast, it can be used with a huge number of items.
	int SortedRatios[10];		// Index of ratios
	float Ratios[10];			// Ratios themselves
	float tmp1;			
	int volumeLeft = MAXVOLUME;
	int weightLeft = MAXWEIGHT;
	int totalValue = 0;
	int i, j;

	// Calculate the ratios for each items
	for (i=0; i < 10; i++) {
		Ratios[i] = (float)itemValue[i] / itemWeight[i];
		SortedRatios[i] = i;
	}

	// Sort them using a Bubble Sort (check for wiki for more details)
	for (i=0; i < linecount; i++)
		for (j=i; j < linecount; j++) {
			if (Ratios[i] < Ratios[j]) {
				// Swap ratios
				tmp1 = Ratios[i];
				Ratios[i] = Ratios[j];
				Ratios[j] = tmp1;

				tmp1 = SortedRatios[i];
				SortedRatios[i] = SortedRatios[j];
				SortedRatios[j] = tmp1;
			}
		}

	// Adding items with the best value/weight ratio first, and add others until we reach the weight limit.
	// Display each item as soon as we add them to the sack.
	i = 0;
	while (weightLeft > 0) {
		// We make sure that the next combination won't make us go over the Volume & Weight limits that we have fixed
		if ((volumeLeft - itemVolume[SortedRatios[i]] >= 0) && (weightLeft - itemWeight[SortedRatios[i]] >= 0)) {
			// We are not going to reach the limit, so we add the item in the sack
			volumeLeft -= itemVolume[SortedRatios[i]];	
			weightLeft -= itemWeight[SortedRatios[i]];		
			std::cout << "Added item #: " << setw (5) << SortedRatios[i] + 1 << "     Value: " << itemValue[SortedRatios[i]] << "   Volume: " << itemVolume[SortedRatios[i]] << "   Weight: " << itemWeight[SortedRatios[i]] << std::endl;
			totalValue += itemValue[SortedRatios[i]];
			i++;
		}
		else {
			break;
		}
	}
	
	std::cout << endl;
	std::cout << "Total Volume: " << setw (5) << knapSack_Max_Volume - volumeLeft << std::endl;
	std::cout << "Total Weight: " << setw (5) << knapSack_Max_Weight - weightLeft << std::endl;
	std::cout << "Total Value:  " << setw (5) << totalValue << std::endl;
	std::cout << endl << endl;
}

Open in new window

DifferentDataSet.jpg
DifferentDataSet-Excel.jpg
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34948068

Final question... how come the sorting order changed from (1, 3, 6, 10) to (3, 6, 1, 10).    'Just curious

It's because in the Greedy function, items are sorted by highest ratio VALUE vs WEIGHT.

Let me check for the problem about 13 items...
0
 

Author Comment

by:ExpExchHelp
ID: 34948132
cdebel:

Gotcha on the sorting....

Thanks for looking into the other scenario.   I truly appreciate it.

EEH
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34948142
ok... there's some stuffs that slips out of my hands.  Sorry for that.

Search for every "10" in your file... you will notice that in a loop, i should have specified "linecount" (just like the other FOR loops).  

At line 85 in your code, it should be: for (i=0; i < linecount; i++)

Line 76 and 77 are also wrong because i hardcoded 10.  But you can't use linecount (a variable) to define the array size.  So you could define them as pointer, and dynamically resize the array based on line count like this:

      int *SortedRatios;            // Index of ratios
      float *Ratios;                  // Ratios themselves
      SortedRatios = new int[linecount];
      Ratios = new float[linecount];

But it's not the only problem, i need a little more time to find what's going on
0
 

Author Comment

by:ExpExchHelp
ID: 34948816
cdebel:

Yes, that actually fixed some access violation errors.    Up until this change, the program 'blew up" (after it produced the output).

Even after this change though, the data set having 13 records does NOT produce the optimal output as the data set having 10 records did.

I'm wondering if the first data set provided the optimal solution by mere coincidence or if indeed it used "brute force" to determine it.   If the latter is the case, I don't know why it didn't work for the second data set.

I'm just a bit baffled... any final suggestions?

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34950694
cdebel:

I think I understand as to why the solution for data set #1 and data set #2 result in an optimal and not optimal solution, respectively.

In data set #1, the values for weight and volume and nearly identical except for items 9 and 10.    That is NOT the case at all for data set #2.

Once I reviewed the code again, I noticed that the ratio was computed only based on weight.
I changed it to include "volume" as well.  See code below.


Once that was done, the output for data set #1 remained unchanged (given that the ratio didn't change except a tiny bit due to items 9 and 10).  

However, the output for data set #2 changed and came much "closer" to the optimal solution.   Essentially, the total value changed from 960 to 1655.   Obviously, it is still off by 300+ from optimal solution (see Excel's answer of 1980), but I at least know that my solution only contains the "Greedy" method.

This definitely concludes my questions regarding the Greedy.   If you are interested (or even have time), I'd post another question that addresses the "Local Search" method.  
http://en.wikipedia.org/wiki/Local_search_%28constraint_satisfaction%29

Essentially, in this approach, an algorithm is designed to swap, e.g., 2 items at the same and compare if the total value has improved.    

Let me know.

EEH




Ratios[i] = (float)itemValue[i] / itemWeight[i];

Ratios[i] = (float)itemValue[i] / (itemVolume[i] + itemWeight[i]);

Open in new window

0
 
LVL 10

Expert Comment

by:cdebel
ID: 34951304
It was not the only problem.  There was a problem with the index.
At the end i was incrementing the "i" variable only if i could place an item in the sack.  But it was not right to do that because it's sorted by ratio, not by weight.   So other items could have been placed in the sack.  So i've modified this piece of code.  I've also added your ratio based on volume and weight.  The result i get is a value of 1805, weight of 680, and Volume of 950.

 
void knapsackGreedy01() {
	// This function will create a knapsack using a greedy method:  That mean that it build a 
	// table of ratios "Value/Weight", then it sort it in descending order to have the highest
	// ratio on top.  Once it's done, it add 1 item of each until there's no more space for 
	// the next item.
	//
	// It might leave the knapsack with some free space and nothing else to fill up because every other
	// items weight are too high.  Therefore, this method is not optimal and could benefit from Local Search
	// function.
	//
	// Since this method is really fast, it can be used with a huge number of items.
	int *SortedRatios;		// Index of ratios
	float *Ratios;			// Ratios themselves
	float tmp1;					
	int weightLeft = MAXWEIGHT;
	int volLeft = MAXVOLUME;
	int totalValue = 0;
	int i, j;

	SortedRatios = new int[linecount];
	Ratios = new float[linecount];

	// Calculate the ratios for each items
	for (i=0; i < linecount; i++) {
		Ratios[i] = (float)itemValue[i] / (itemVolume[i] + itemWeight[i]);
		SortedRatios[i] = i;
	}

	// Sort them using a Bubble Sort (check for wiki for more details)
	for (i=0; i < linecount; i++)
		for (j=i; j < linecount; j++) {
			if (Ratios[i] < Ratios[j]) {
				// Swap ratios
				tmp1 = Ratios[i];
				Ratios[i] = Ratios[j];
				Ratios[j] = tmp1;

				tmp1 = SortedRatios[i];
				SortedRatios[i] = SortedRatios[j];
				SortedRatios[j] = tmp1;
			}
		}

	// This code is used to show the Bubble Sort result to see if it's sorted per ratio properly
	//std::cout << "Tableau des ratios" << std::endl;
	//for (i=0; i<linecount; i++) {
	//	std::cout << "Ratios: " << Ratios[i] << ", Index: " << SortedRatios[i] << ", Weight: " << itemWeight[SortedRatios[i]] << ", Value: " << itemValue[SortedRatios[i]]  << ", Volume: " << itemVolume[SortedRatios[i]] << std::endl;
	//}
	//std::cout << std::endl << std::endl;

	// Adding items with the best value/weight ratio first, and add others until we reach the weight limit.
	// Display each item as soon as we add them to the sack.
	i = 0;
	while ((weightLeft > 0) && (volLeft > 0) && (i < linecount)) {
		// We make sure that the next combination won't make us go over the Volume & Weight limits that we have fixed
		if ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volLeft - itemVolume[SortedRatios[i]] >= 0)) {
			// We are not going to reach the limit, so we add the item in the sack
			weightLeft -= itemWeight[SortedRatios[i]];
			volLeft -= itemVolume[SortedRatios[i]];			
			std::cout << "Added item #" << SortedRatios[i] + 1 << "  Weight: " << itemWeight[ SortedRatios[i]] << ", Volume: " << itemVolume[ SortedRatios[i]] << ", Value: " << itemValue[ SortedRatios[i]] << std::endl;
			totalValue += itemValue[ SortedRatios[i]];
		}
		i++;
	}
	std::cout << "Total Weight: " << knapSack_Max_Weight - weightLeft << std::endl;
	std::cout << "Total Volume: " << knapSack_Max_Volume - volLeft << std::endl;
	std::cout << "Total Value: " << totalValue << std::endl;
}

Open in new window


Post another question.  I'll add you in the list of people that i'll follow.  If no one answer, might give it a try but for the moment i got to do some work.
0
 

Author Comment

by:ExpExchHelp
ID: 34952271
cdebel:

Thanks... that's awesome... the optimal value (1805) of the second data set (I presume) is very close to the "real" optimal value.    

I don't have C++ here at work... but I will check it out asap tonight.    Again, thanks for continuing to monitor this thread and offering your help.    I am very grateful for that.

I'll do further reading on the "Local Search".    I'm trying to meet my work deadline for early next week... but hey, that's a whole week from now.  

If (more than likely) I get stuck, I'll post another question.    And, thanks, for adding me to the list of people you follow.   'Much appreciated.

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34956324
cdebel:

Got it... that's a big improvement (total value of 1805).    I also like the "Tableau des ratios".    That's definitely a "keeper".   8)

As mentioned, I'll do more research on the "local search".    I'll keep you posted.

EEH
0
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 

Author Comment

by:ExpExchHelp
ID: 34956458
Sorry... one more quick one.

Per snapshot below... how do I include rounding to two decimals?
std::cout << "Ratios: " << setw (8) << Ratios[i] << setw (10) << "Index: " << setw (2) << SortedRatios[i] ....

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34956465
Forgot the snapshot... see previous posting.
Rounding.jpg
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34956950
You got to fly with your own wings buddy :)  Have you forgot how to make a search on google or E-E? :-)

I've not programmed in C++ since 10 years.

But here is your answer (found on google).  Check at the FIXED and SETPRECISION in the code bellow:

 
std::cout << "Ratios: " << fixed << setprecision(2) << Ratios[i] << std::endl;

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34957036
cdebel:

You're right... but I'm learning.    I tried several different methods incl. to actually modify the format during the computation.    

I certainly did not want to abuse your help...  ;)

EEH

P.S.  For not having programmed in C++ for 10 years, you seem to have not forgotten much.   I'd have thought you're doing this for a living.   8)
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34957090
I do computer programming for living, but i've not used this language for years.

I mainly use C#, VB.NET, and ASP.NET at the moment.

I've not used C++, COBOL and some other languages since years.  

Just to give you an idea: i knew there was a command "COUT" to display some text, and PRINTF... but i didn't remembered how to use them.
0
 

Author Comment

by:ExpExchHelp
ID: 34957839
cdebel:

Cool... I wish I had the "smarts" for being a programmer.    However, I'm learning right now... I guess that's the most important thing, right.   Open expand your mind to new options.


Ok... 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
0
 

Author Comment

by:ExpExchHelp
ID: 34966959
The posting http://www.experts-exchange.com/Programming/Languages/CPP/Q_26840869.html
is somewhat of a long thread.  

Given your familiarity of this program, could you please provide me a basic hint as to how I can achieve the following:

1. Select an item (randomly) that has been added to the knapsack.
2. Select an item that is NOT in the knapsack.
3. Swap them (meaning replacing the two selected items).   Compute the new total value.   If the value is greater, keep the new item.   Otherwise, take it out and return the original item.
4. Repeat steps 1 to 3.   Stop after n iterations.

I'm just not sure how to get started.   W/ a few hints, I might be able getting somewhere.   8)

EEH

P.S.   I've done my "homework" on "Local Search"... just not finding good tips online for actually implementing the algorithm.
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34969318
I know it's for your course, i've watched some of your thread where some people refuse to help because E-E is not there to do your homework.

The 4 steps that you have mentionned are ok.  All you need now is to translate this into C++... this is the easiest part.  If you get any question on C++ programming, for example, if you don't know how to generate random numbers, then feel free to ask.

You already know that you got to create a loop to stop after N iteration.  So you got to do a Do While or something like that.
In that loop, you know that you need to have 2 random numbers to access your array.  One should give you the index of an item that is in your sack, the other point to an item that is not in the sack.  So you know that you have to put these items into 2 different array, or sort them.  To get a random number, you can use srand and rand functions.  Google if you don't know how to use them, it's quite easy to find.
You already know how to compute what it's in your sack.  You already got the array with volume & weight.

You know how to make a loop, how to access an array, etc... so go ahead.

If this is not for your homework, then maybe the company you are working for need to pay someone to give you some help with the coding if you are not a programmer yourself.
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34969334
Oh and by the way, what sdeller said about the Bubble Sort in the other post, of course this is not the best method on earth.  But since you have shown only few data (10 and 13 data only), Bubble Sort is the easiest method to remember.

There's more advanced techniques to sort things, but why the hell would i have wrote code for a balanced tree when 2 stupid loops do the job? neh!
0
 

Author Comment

by:ExpExchHelp
ID: 34970809
cdebel:

Thanks for the hints.... every time I hear the term "arrays" I choke (smile).  

I'll check it out the next couple of days/nights... definitely this weekend.    I'm sure I get something going.  

If I do have questions, I feel bad posting them here since this question is officially closed.    I just want to make sure you get the recognition for the help that you provide me.

EEH
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34970901
If you feel bad, just post another question.  But like many other says, your question should should be about a specific subject, and you should already have some code or tried something before posting.  Never ask a question where you ask to experts to give you the answer from A to Z.

Computer programming is essentialy:
- Iteration
- Arrays
- Pointers
- Database Request
- Display

If you have difficulties with these concepts, then maybe you are not fit for computer programming.  You got to understand those concepts.  

If you are doing this for your courses at school, then you just post-pone the problem...  you won't fail now at your courses, but you will fail later at your job.  
0
 

Author Comment

by:ExpExchHelp
ID: 34972110
cdebel:

Good advice... based on your recommendations, I'll attempt to come up w/ a structure on the Local Search.

Will keep you posted.

Thanks again for the hints earlier.

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34985361
cdebel:

I'm trying to pass the computed values from the function"Greedy" to "LocalSearch".   See code below.

I'm not sure if I used the proper method/syntax.    Right now, the cout statement "This is a test!" does NOT print.

Do you mind providing me a hint on this?   I've actually opened another question at:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_26849260.html

Thanks,
EEH
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft) {

	int i, j;
	

	i = 0;
	while ((weightLeft > 0) && (volumeLeft > 0) && (i < linecount)) {
		
		// This If-statement ensures that the next item combination (volume & weight) will NOT violate either constraint.
		if ((volumeLeft - itemVolume[SortedRatios[i]] >= 0) && (weightLeft - itemWeight[SortedRatios[i]] >= 0)) {
			
			cout << "This is a test!";
		}
		i++;
	}

}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34986900
Never mind the previous question...

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34987979
cdebel:

<< The 4 steps that you have mentionned are ok.  All you need now is to translate this into C++...>>

Well, seems like I'm struggling a bit w/ the translation.    I have an open question which the specifics.

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

Any chance you might have a look?

Thanks,
EEH
0
 
LVL 10

Expert Comment

by:cdebel
ID: 34991509
It says that the question have been deleted.  

If you got any request, please check at my profile.   You can email me if you need me to check at one of your question.  

We shouldn't use this thread anymore, it's closed and we are "poluting" this answer.
0
 

Author Comment

by:ExpExchHelp
ID: 35210917
cdebel:

Hello again... I hope you're still getting notified when updates are made to a message.

You provided me some awesome help (about a month ago).  

I've run the problem with different data sets now and I'm getting a strange output (a negative delta returns some 10-digit number vs. the actual difference).

I've posted a new question at:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_26910016.html

Given that you are "quite familiar" with the code, maybe you know how to solve this problem.

Thanks,
EEH
0
 

Author Comment

by:ExpExchHelp
ID: 35214883
Netminder:

I have no idea what you're talking about!!

Cdebel helped me (in this thread) to come up w/ a solution.    I don't know why you'd make a reference to e.g. "email".    

As a paying member, I appreicate your guidance on proper forum mgmt... but please dont' make up stuff!
0
 
LVL 10

Expert Comment

by:cdebel
ID: 35215996
Netminder, may i ask you what you have read in this solution?  You spotted the word "EMAIL" and decided to slam us because we dare pronounced that word?  I do agree with ExpExchHelp on that, you are really making up stuff!

If you check at my last comment, i said something like:  "You already got the answer, if you need me to check at other thread, just send me an email"

Why the hell E-E would accept that their users come up here and say: "Hey, I've posted another question somewhere else and nobody seems to help.  You seems to have some knowledge of my code and about the subject i'm working on, could you take a look at it?".  

If E-E accept that, then it mean that it accept that all their solutions to become a total junkyard!   Like our actual comments... which is absolutely not necessary to this question.  So if someone come up on E-E and check at this solution, the first words that will come up to their mind is: "What the heck!?!?"

Oh and NetMinder, i'm also a paying member.  The only reason why i helped is because I WANTED TO HELP.   That's all...  We didn't exchanged any email, and as you can see, ExpExchHelp posted a new thread and asked me to take a look at it here, that should ring you a bell that he didn't mailed me!   Understood Sherlock?
0
 
LVL 10

Expert Comment

by:cdebel
ID: 35216070
Netminder: And if you think that my last comment has a total lack of profesionnalism, the way that you have threated me is TOTALLY NOT PROFESSIONNAL.  

I will not accept that kind of behavior.  If you insult people, expect them to punch back!

The next time that you snap me with that kind of shit, don't think i'll leave that behind and accept that.
Repeated violations are considered an abuse of EE's systems, and the behavior will result in consequences.

At least, you should explain yourself.  I can't understand that you arrived to the conclusion that we emailed each other when ExpExchHelp keep asking me to check at other thread PUBLICLY, HERE IN THIS THREAD.   (See those comments for yourself: 35210917, 34987979, 34985361)

For your info, i've just created a PDF file in case you decide to delete this thread.  Because if i get that kind of shit again, i'll gladly give a call to Experts-Exchange.
0
 
LVL 10

Expert Comment

by:cdebel
ID: 35216218
Netminder: Have you tried to email me this morning? LMAO :-)
0
 

Author Comment

by:ExpExchHelp
ID: 35216359
Netminder:

I completely concur with cdebel.    To put it in simple terms... I've placed references/URLs to another question in this THREAD.    Why on earth would I do it if email exchange has taken place?    Again, you jumped at conclusion!!

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 35216383
cdebel:

No, I actually sent out the email with a reference to another question.     My bet if what was confusing.  

I will post new URL here again.

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 35216578
Please check out new question... if time permits.

http://www.experts-exchange.com/Programming/Languages/CPP/Q_26911869.html
0
 
LVL 10

Expert Comment

by:cdebel
ID: 35217225
Netminder: Saying to someone "Repeated violations are considered an abuse of EE's systems" mean that we have cheated, violated any rule.  If you didn't mean that, then your comment was absolutely irrelevant and you didn't had to say that.  So from that, i assume that you treated us as cheaters.

I was not aware that it was against Term Of Use to post links to other web sites, especially when this site explain the basics of what a user is trying to implement but doesn't have the knowledge to program it himself.  For example, the link that ExpExchHelp posted about Wiki.   I don't consider it offensive but strictly speaking, it's going against the Term Of Use according to what you said.  But i do agree that if the link lead to the solution (and nothing to clarify the question), then yes, Link should not be used because it often lead to deleted thread in other forums and that would cause some frustration to your users who are looking for that answer.

The only thing that i can suggest is to point out who this notice is for next time.  
Also, try to point out the problem itself, if you have proofs of course or enough elements for suspicions.  Because like i said, if you follow every comments of this thread, you will notice that he asked for my help here many times (to check at other threads that he created here).  If he would have emailed them to me, he wouldn,t have posted them here (make sense?)... so your comment about emailing each other was just irrelevant.  

Now that you throw up that comment about academic stuff, that can piss you off and i understand.  I've noticed nothing here that could have made me think that it was academic.  In fact, i didn't really thought about what could make me think of which comment in a question could make me feel like it's an academic question.  So if you have stuff to talk to each other, then fine... but try to specify who you are talking to instead of firing at will blindly.

And about "Ask a related question", i've never noticed that option until you pointed that in your last comment.  I'll probably use it so thanks for the info.

And yes, i've chatted with the customer support, and for your info, yes i'm paying... no mather if i've got the premium status or not, i'm still beeing billed.  I think that the premium status is only there to say: "You got enough point to stop paying"... but as soon as you stop answering question, you get billed.  
0
 

Author Comment

by:ExpExchHelp
ID: 35219913
Holy camolie... a can of worms has been opened.    Not sure if I can/want to read all of the "essays".  8)
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

758 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

20 Experts available now in Live!

Get 1:1 Help Now