C++ Algorithm

Hello C++ Experts:

I've implemented an algorithm -- in C++ -- with the help of a few EE gurus.    The code for this "0-1 knapsack" problem is posted below.

Now, the current program/solution follows the "Greedy" method (comments inside the code provide more details).    In this program, the method simply looks at the largest "ratio" (computed via "Value / (Volume + Weight)" and adds items into the "knapsack" until it reaches either one of the two constraints ("maximum volume" or "maximum weight" of the knapsack).

Now, I'm using two different data sets (both of them are included in the declaration section).   Using the first data set, it just mere coincidence that the greedy method results in an optimal solution with no slack (unused volume/weight capacity).   Therefore, I'm indeed outputting the optimal solution -- a value that I verified using MS-Excel's "Solver".

However, the second data set leaves unused capacity.    In contrast to MS-Excel's solver, my current C++ program does NOT attempt to optimize the solution by "swapping" (potentially items).    

Well, as you know, a "picture is worth a thousand words", so I decided to provide more details in the attached spreadsheet.   The XLS contains four (4) worksheets:
1. "Excel Solver -- Data Set 1"
2. "Excel Solver -- Data Set 2"
3. "C++ Snapshots of 2 Data Sets"
4. "C++ Logic"

The first three worksheets could be considered more or less FYI.   Nevertheless, they set the stage and provide a quick contrast between the two data sets as well as the C++ output (snapshots).

The fourth worksheet, however, provides IMHO the meat of what I'm trying to accomplish.

Essentially, I need to come up with a "Local Search" algorithm that will accept a worse solution/option in order to get out of a "local optimum" in order to reach a "global optimum".    There's plenty of detail on the web... search keywords such as "local search algorithm" return valuable info, incl. a 2010 reference document such as shown at:
http://www.cs.umd.edu/~nau/cmsc421/chapter04b.pdf   

Based on the URL, slide #7 ("Hill climbing" ) outlines -- in much better words/pictures -- what I described in the previous paragraph.

So, what do I need some help with?    In addition to my greedy algorithm (see the C++ code), I'd like to implement the "Local Search" algorithm which would allow the swapping of, e.g., item #7 with item #10.   [What?!?!   ... where's this coming from... well, please read the info in the yellow call-out box on worksheet "C++ Logic" of the attached XLS].

Again, any help is appreciated for achieving this goal.   Thousand thanks in advance!!!

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 (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) ******


// Declarations of independent functions
void knapsack_Greedy_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 weightLeft = MAXWEIGHT;
	int volumeLeft = 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 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 ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volumeLeft - itemVolume[SortedRatios[i]] >= 0)) {
			
			// Passing the If-statement ensure that space is left in the knapsack.  Therefore, the item is added to the knapsack.
			weightLeft -= itemWeight[SortedRatios[i]];
			volumeLeft -= itemVolume[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;
}

Select allOpen in new window

Data-Set-1-vs.-Data-Set-2----plu.xls