C++ -- Passing Variable Between Functions

As far as I can tell, your code isn't actually calling the local search algorithm, so how are you testing it?

crysallus:

You're right... I missed that step...  I've added code to lines:

- 54
- 177

Obviously, that didn't do it as I still don't show the test message.   What am I missing?   Do I need to include all the variable names in the parenthesis?   If yes, did I do it correctly?

EEH

// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>                                                                                    
#include <limits.h>
using namespace std;


// Declaration of variables
#define MAXVOLUME 800															// Knapsack's maximum volume (constant)										
int knapSack_Max_Volume = 800;													// Knapsack's maximum volume 

#define MAXWEIGHT 900															// Knapsack's maximum weight (constant)
int knapSack_Max_Weight = 900;													// Knapsack's maximum weight 
									
int linecount = 10;																// The number of items available for selection
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Knapsack items' array specifing their value
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Knapsack items' array specifing their volume
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Knapsack items' array specifing their weight


// ****** Begin of TESTING DATA #1 (other than the data provided) ******
/*#define MAXVOLUME 1100
int knapSack_Max_Volume = 1100;

#define MAXWEIGHT 1400
int knapSack_Max_Weight = 1400;	
								
int linecount = 13;																		
int itemValue[13]  = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50};		
int itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200};	
int itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200};	*/	
// ****** End of TESTING DATA (other than the data provided) ******


// ****** Begin of TESTING DATA #2 (other than the data provided) ******
/*#define MAXVOLUME 1900
int knapSack_Max_Volume = 1900;

#define MAXWEIGHT 1700
int knapSack_Max_Weight = 1700;	
								
int linecount = 22;																		
int itemValue[22]  = {100, 150, 70, 80, 90, 95, 220, 30, 60, 200, 80, 140, 250, 225, 60, 65, 40, 20, 25, 100, 30, 10};		
int itemVolume[22] = {120, 200, 250, 170, 175, 225, 400, 80, 180, 135, 110, 205, 395, 415, 25, 155, 25, 15, 55, 315, 55, 260};	
int itemWeight[22] = {130, 185, 200, 100, 200, 200, 420, 40, 140, 200, 150, 200, 395, 400, 50, 100, 10, 10, 100, 325, 60, 270};*/		
// ****** End of TESTING DATA (other than the data provided) ******


// Declarations of independent functions
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm();


// Structure used in the knapsack problem
typedef struct PossibleMatch {
	int nItem;
	int nValue;
	int nVolume;
	int nWeight;
}  ;


// Main() is the programs' "entry point"
int main()
{		
	// Function call to execute the "greedy" algorithm for the "0-1 Knapsack Problem:
	// More information can be obtained via:  
	// 1. http://en.wikipedia.org/wiki/Greedy_algorithm
	// 2. http://en.wikipedia.org/wiki/Knapsack_problem
	knapsack_Greedy_Algorithm();

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


void knapsack_Greedy_Algorithm() {
	// ********************** General Summary of the implemented Greedy Algorithm *********************
	// This function will add items into a knapsack using a "greedy" algorithm.  
	// This algorithm first computes/fills a table/array holding ratios of "Value / (Volume + Weight)".
	// Then, the ratio is sorted in descending order (holding the largest ratios first). 
	// Once the ratio table has been computed, the algorithm loops through the table/arry
	// and adds items until there reaching the constraints (volume and weight constraints).
	// In other words, it adds items until there is no more space for the next item.
	// Depending on the data sets, there is a probability that the knapsack is left with 
	// additional available space  (both volume or weight).  
	// Therefore, this method is NOT optimal and could benefit from the "Local Search" function.
	// ************************************************************************************************


	// This algorithm computes very fast, so it can be used with a significant large number of items
	int *SortedRatios;							// Index of ratios
	float *Ratios;								// Ratios themselves
	float tmp1;					
	int volumeLeft = MAXVOLUME;
	int weightLeft = MAXWEIGHT;
	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 the ratios using a "Bubble Sort"
	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;
			}
		}


	// Console output of the Bubble Sort result in order to see if it is properly sorted (by ratio)
	std::cout << endl;
	std::cout << "Step 1: Ratio Computation:" << std::endl;
	std::cout << "==========================" << std::endl << endl;
		for (i=0; i<linecount; i++) {
			std::cout << "Ratio: " << setw (2) << fixed << setprecision(2) << Ratios[i] << setw (10) << "Index: " << setw (2) << SortedRatios[i] << setw (10) << "Value: " << setw (3) << itemValue[SortedRatios[i]] << setw (11) << "Volume: " << setw (3) << itemVolume[SortedRatios[i]]  << setw (11) << "Weight: " << setw (3) << itemWeight[SortedRatios[i]] << std::endl;
		}
	std::cout << endl << endl;

	
	// Items are added to the knapsack until the volume/weight constraints are met.  Items are added in DESC order of the computed ratio.
	std::cout << endl;
	std::cout << "Step 2: The selected knapsack items are as follows:" << std::endl;
	std::cout << "===================================================" << std::endl << endl;	

	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)) {
			
			// Having "passed" the If-statement ensures that capacity (for both volume & weight) is left in the knapsack.  Therefore, an item is added to the knapsack.
			volumeLeft -= itemVolume[SortedRatios[i]];	
			weightLeft -= itemWeight[SortedRatios[i]];	
			std::cout << "Item# " << setw (2) << SortedRatios[i] + 1 << "  --  Value: " << setw (3) << itemValue[SortedRatios[i]] << "   Volume: " << setw (3) << itemVolume[SortedRatios[i]] << "   Weight: " << setw (3) << itemWeight[SortedRatios[i]] << std::endl;
			totalValue += itemValue[ SortedRatios[i]];
		}
		i++;
	}

	// Console output providing the knapsack's inventory (including "Total Value" of the items; total volume/weight of the items).
	std::cout << endl << endl << endl;
	std::cout << "Step 3: Knapsack 'Inventory':" << std::endl;
	std::cout << "=============================" << std::endl << endl;	
	std::cout << "Total Knapsack Value:     " << setw (3) << totalValue << std::endl;
	std::cout << endl;
	std::cout << "Total Volume (available): " << setw (4) << knapSack_Max_Volume << std::endl;
	std::cout << "Total Volume (used):      " << setw (4) << knapSack_Max_Volume - volumeLeft << std::endl;
	std::cout << "Volume Capacity (left):   " << setw (4) << volumeLeft << std::endl;
	std::cout << endl;
	std::cout << "Total Weight (available): " << setw (4) << knapSack_Max_Weight << std::endl;
	std::cout << "Total Weight (used):      " << setw (4) << knapSack_Max_Weight - weightLeft << std::endl;
	std::cout << "Weight Capacity (left):   " << setw (4) << weightLeft << std::endl;
	std::cout << endl << endl << endl;


	// Call the LocalSearch function
    void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft);	
}


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

}

Select allOpen in new window

You need to include the type list in the declaration on line 54. The variable names themselves are optional, but I prefer to leave them in as it makes it clearer what the function does. eg.

void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft);

Select allOpen in new window

When calling the method on 177, don't include the types:

knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, volumeLeft, weightLeft);

Select allOpen in new window

I just tested your code, and you won't see the message printed if the knapsack is already full i.e. if weightLeft or volumeLeft has already reached 0 (which they are with your current test data), as the while loop condition is false to start with.

Is the local search algorithm meant to be a second-stage in the process, following on from the greedy search, or are they meant to be 2 separate algorithms to solve the same problem?

crysallus:

I made the suggested changes to lines 54 and 177.

And, yes, you're right... for this data set, the volume/weight will be 0.   Therefore, for testing purposes, I changed the while loop as shown below.    Still, it doesn't print the statement.

What else am I overlooking?

EEH

P.S.  Yes, the "LocalSearch" is a continuation of the Greedy.   Depending on the data set, I will or will not hit the optimal solution with the Greedy algorithm alone.   I'm trying to now look into some methods where I swap items.    

For instance, I might create a more optimal "total value" by taking out 1 item from the knapsack and replace it with another item.    For this process, I simply want to make all previously computed information "available" in the LocalSearch.      

Assuming the test msg will print, will this work by passing on the last recent computed value (weights used, weights left, etc.)?

Changed from:

while ((weightLeft > 0) && (volumeLeft > 0) && (i < linecount)) {

to:
while ((weightLeft = 0) && (volumeLeft = 0)) {

Select allOpen in new window

crysallus:

Great... that'll work for me.    Thanks for the good advice.    Looks like everything is passed properly.

Just to be certain though... I don't have to be concerned about having "lost" pointers reference, etc?   Essentially, based on statement below (code section), am I passing all information from Greedy to LocalSearch?

EEH

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

Select allOpen in new window

Thanks for the prompt help!!!   Much appreciated.

No. I don't think so.

In fact, as you're still learning C++, I'd suggest you avoid the complexity of pointers and dynamic memory management unless you really need to use them, which you actually don't for the code you've provided above. To avoid the need for pointers, firstly change linecount to be a constant eg:

const int LINE_COUNT = 10; 
int itemValue[LINE_COUNT]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};
int itemVolume[LINE_COUNT] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};
int itemWeight[LINE_COUNT] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};

Select allOpen in new window

I changed it to be all capitals, as that's fairly typical programming practice, though not necessary, so you don't have to do that if you don't want. Others prefer just to put a 'k' at the start of the variable name to indicate that it's constant. If you change the name, you would of course have to change it all throughout the code as well.

Then you can simply use arrays. Eg. in greedy function:

int SortedRatios[LINE_COUNT];
float Ratios[LINE_COUNT];

Select allOpen in new window

No need for:

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

Select allOpen in new window

And the local algorithm method signature would become:

void knapsack_LocalSearch_Algorithm(int SortedRatios[], float Ratios[], float tmp1, int volumeLeft, int weightLeft);

Select allOpen in new window

That way there's no need for you to worry about allocating/freeing dynamic memory, or using pointers directly.

If you stick with the dynamic memory though (eg. SortedRatios = new int[linecount]), then you need to delete them, which you haven't done, by putting

delete [] SortedRatios; 

Select allOpen in new window

at the bottom of knapsack_Greedy_Algorithm (and the same for Ratios). Just make sure you don't delete them before passing them to the local algorithm, do it after.