Solved

C++ Arrays

Posted on 2011-02-26
22
280 Views
Last Modified: 2012-06-21
I have a program that generates the required output based on a "selection" algorithm (see lines 1 through 178).

I've now added a 2nd function (lines 181 through 242).   This second function shall act as an extension to the first function (e.g., potentially improving the total value).

Right now, I want to achieve the following:   Based on the code (lines 145 through 158):
- put the selected items into array #1 (items currently in the "knapsack")
- put the non-selected items into array #2 (items NOT in the "knapsack")

I've not created these arrays yet... for testing purposes, however, I simply want to use an IF-Else statement (or another appropriate method) to print to the console:  

Can someone please provide me some assistance for modifying the code (see lines 208 through 240) allowing to accomplish the following?

a.  Items are currently in the knapsack:
2
11
7
3
4
1

b. The following items are NOT in the knapsack:
5
6
8
9
10
12

Thank you,
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(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);


// 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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

	int i, j;
	
	cout << "****************************************************" << endl << endl;
	cout << "Testing Value Passing (from Greedy function to Local Search function):" << endl;

	cout << "Total Value: " << totalValue << endl << endl;

	cout << "Max Volume: "  << knapSack_Max_Volume << endl;
	cout << "Volume Used: " << knapSack_Max_Volume - volumeLeft << endl;
	cout << "Volume Left: " << volumeLeft << endl << endl;

	cout << "Max Weight: "  << knapSack_Max_Weight << endl;
	cout << "Weight Used: " << knapSack_Max_Weight - weightLeft << endl;
	cout << "Weight Left: " << weightLeft << endl << endl;
	
	for (int i = 0; i < linecount; i++)
		cout << SortedRatios[i] << endl;
		cout << endl;

	for (int i = 0; i < linecount; i++)
		cout << setw (3) << Ratios[i] << endl;
		cout << 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)) {
			
			cout << "Testing While Loop:" << endl;

			for (int i = 0; i < linecount; i++)
			cout << SortedRatios[i] << endl;
			cout << endl;
		}
		i++;
	}



	//if ((volumeLeft >= 0) && (weightLeft >= 0)) {
	//	
	//	cout << "If #1" << endl;
	//	cout << endl << endl;
	//	
	//	for (int i = 0; i < linecount; i++)
	//		cout << SortedRatios[i] << endl;
	//		cout << endl;

	//}

	//else {

	//	cout << "Else #2" << endl;
	//	cout << endl << endl;
	//}

}

Open in new window

ItemsInKnapsack.jpg
0
Comment
Question by:ExpExchHelp
  • 12
  • 10
22 Comments
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34989497
Man, i didn't quite understand what you want but i did this.
See if it's what you want.
0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34989499
Forgot the source..
 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#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) ******



struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

deque<knapsack_Item> SortedItems;

// Declarations of independent functions
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);


// 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;
        knapsack_Item kI;
        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)) {

                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    SortedItems.push_back(kI);

                        // 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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

        int i, j;

        cout << "****************************************************" << endl << endl;
        cout << "Testing Value Passing (from Greedy function to Local Search function):" << endl;

        cout << "Total Value: " << totalValue << endl << endl;

        cout << "Max Volume: "  << knapSack_Max_Volume << endl;
        cout << "Volume Used: " << knapSack_Max_Volume - volumeLeft << endl;
        cout << "Volume Left: " << volumeLeft << endl << endl;

        cout << "Max Weight: "  << knapSack_Max_Weight << endl;
        cout << "Weight Used: " << knapSack_Max_Weight - weightLeft << endl;
        cout << "Weight Left: " << weightLeft << endl << endl;

        for (int i = 0; i < linecount; i++)
                cout << SortedRatios[i] << endl;
                cout << endl;

        for (int i = 0; i < linecount; i++)
                cout << setw (3) << Ratios[i] << endl;
                cout << endl;



        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl << endl;
            it++;
        }


}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34989851
sergiobg57:

Sorry for the confusion... I've attached a spreadsheet that (hopefully) will facilitate what I'm trying to achieve.   Allow me to briefly recap what's in the XLS... and how it pertains to the C++ problem.

It includes three worksheets:
1. "Excel Solver -- Data Set 2" -- if you're familiar with MS-Excel Solver (Tools | Solver), you notice that the goal is to maximize the total value (cell E21).  

2. "C++ Snapshot of Data Set 2" -- displays the C++ output that I'm achieving when running the program with the Greedy algorithm (original lines of code 1 through 177)

3. "C++ Logic" -- this worksheet is intended to further illustrate what I'm trying to achieve in C++.   Per the first worksheet (using Solver), the optimal total value (of the knapsack) equals 1,980 value units.   However, per the second worksheet, the C++'s optimal value solution results in 1,805 total value units.

So, the Excel solution is better by 175 value units.   Why is that?   Excel uses an optimization algorithm that "looks" at reducing slack (in this case for volume and weight).   The XLS "removed" item #7 from the knapsack... by doing so, it freed up 50 volume units and 25 weights units.    As a result, a larger item (#10) could fit into the knapsack thereby adding 250 value units back into the knapsack.  

So, essentially, by swapping the originally selected item #7 and replacing it w/ the originally non-selected item #10, there's a value net gain of 175 value points (250 -75).

That's "swapping" is what I'm trying to achieve in the 2nd C++ function.    So, my goal was to first all the selected items into one array and the non-selected items into another array.

Then, I'm hoping to use some random number (up to e.g. 30 iterations) and see and any of these would swap 7 with 10.

Do you have a recommendation for achieving this goal?    I've been really struggling getting this done in C++.

Many thanks in advance!!

EEH
Data-Set-2.xls
0
 

Author Comment

by:ExpExchHelp
ID: 34989880
sergiobg57:

Please see previous post first... it provides additional details.

Quick question though... based on the code below, how does it know where to "stop"... meaning, it only outputs 3, 6, 10, and 1 (which is correct btw).

Again, ultimate goal is described in the previous posting... meanwhile, how could I do the same for printing out the remaining items... in a different array though?




deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            cout << (*it).Index  << endl;
            //cout << "Weight: " << (*it).Weight << endl;
            //cout << "Value: "  << (*it).Value  << endl;
            //cout << "Volume: " << (*it).Volume << endl;
            it++;
        }

Open in new window

0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34989990
Using an iterator is just like using a pointer.
In fact, in this particular case, you can switch it for a pointer arithmetic if you like.

for (int i = 0;i<SortedItems.size();i++)
   cout << SortedItems[i];

Open in new window


If you aren't used to C++'s STL, then deque is just a double linked list for generic data.
 
struct HI{
 HI* prev;
 HI* next;
 UNKNOWN GENERIC_DATA;
};

Open in new window


In fact, you could lessen your source's size using some of STL's algorithms.

Btw, about the excel's solution.. are you sure this solution isn't the optimal?
If it is, then maybe it's not using a greedy algorithm since dynamic programming also solves that same problem better then it's recursive version.
But if you want to optimize, i'll figure something out by tomorrow morning.
At night i'm not a good developer without coffee and today i forgot to buy more coffee. hehe
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#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) ******



struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

deque<knapsack_Item> SortedItems;
deque<knapsack_Item> Left_Behind;

// Declarations of independent functions
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);


// 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;
        knapsack_Item kI;
        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)) {

                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    SortedItems.push_back(kI);

                        // 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]];
                }
                else{
                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    Left_Behind.push_back(kI);
                }
                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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

        int i, j;

        cout << "****************************************************" << endl << endl;
        cout << "Testing Value Passing (from Greedy function to Local Search function):" << endl;

        cout << "Total Value: " << totalValue << endl << endl;

        cout << "Max Volume: "  << knapSack_Max_Volume << endl;
        cout << "Volume Used: " << knapSack_Max_Volume - volumeLeft << endl;
        cout << "Volume Left: " << volumeLeft << endl << endl;

        cout << "Max Weight: "  << knapSack_Max_Weight << endl;
        cout << "Weight Used: " << knapSack_Max_Weight - weightLeft << endl;
        cout << "Weight Left: " << weightLeft << endl << endl;

        for (int i = 0; i < linecount; i++)
                cout << SortedRatios[i] << endl;
                cout << endl;

        for (int i = 0; i < linecount; i++)
                cout << setw (3) << Ratios[i] << endl;
                cout << endl;



        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }
        cout << "==================================================================" << endl;
        it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }


}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34990034
sergiobg57:

Thank you for the prompt reply... I truly appreciate it.

As I'm still learning C++, I will have to do a bit more reading on this.

May I ask if you had a chance to look at the XLS... particularly the 3rd worksheet "C++ Code"?

If yes, do you have a recommendation as to how I can go through n number of iterations and swap out items?     Ideally, I'd end up (randomly) with replacing 7 with 10.   However, even if I don't hit that optimal value (and actually even show a reduction in total value), I am able to demonstrate that my "Local Search" algorithm works.

Thousand thanks in advance,
EEH

0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34990101
I'll cannot tell you a way to do this optimization right now because i really need to sleep.
Here in Brazil it's 1:00 AM.
I'm just online because i'm finishing some works.
Right now i'm really just a zombie in front of a computer coding all night long.
I'll finish my work here, and then i'll figure a way to do this optimization as soon as i wake up.

See ya.
0
 

Author Comment

by:ExpExchHelp
ID: 34991242
sergiobg57:

Thousand thanks in advance... your help is truly appreciate!!!!

EEH
0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34991324
Remember, it'll not always get you to the optimal solution.

It's just and algorithms which optimizes the result by looking if it can shove some item off the knapsack in order to add a larger one.
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#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) ******



struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

deque<knapsack_Item> SortedItems;
deque<knapsack_Item> Left_Behind;

// Declarations of independent functions
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);


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

int volumeLeft = MAXVOLUME;


// 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 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;
        knapsack_Item kI;
        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)) {

                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    SortedItems.push_back(kI);

                        // 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]];
                }
                else{
                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    Left_Behind.push_back(kI);
                }
                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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

        int i, j;

        cout << "****************************************************" << endl << endl;
        cout << "Testing Value Passing (from Greedy function to Local Search function):" << endl;

        cout << "Total Value: " << totalValue << endl << endl;

        cout << "Max Volume: "  << knapSack_Max_Volume << endl;
        cout << "Volume Used: " << knapSack_Max_Volume - volumeLeft << endl;
        cout << "Volume Left: " << volumeLeft << endl << endl;

        cout << "Max Weight: "  << knapSack_Max_Weight << endl;
        cout << "Weight Used: " << knapSack_Max_Weight - weightLeft << endl;
        cout << "Weight Left: " << weightLeft << endl << endl;

        for (int i = 0; i < linecount; i++)
                cout << SortedRatios[i] << endl;
                cout << endl;

        for (int i = 0; i < linecount; i++)
                cout << setw (3) << Ratios[i] << endl;
                cout << endl;



        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }
        cout << "==================================================================" << endl;
        it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }
        unsigned int UsedVolume = knapSack_Max_Volume - volumeLeft;
        unsigned int NewVolume = 0x0;
        for(int i = 0; i < SortedItems.size();i++){
            for(int c = 0; c<Left_Behind.size();c++){
                NewVolume = (UsedVolume - SortedItems[i].Volume) + Left_Behind[c].Volume;
                if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){

                    Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedVolume = NewVolume;



                    if(NewVolume == knapSack_Max_Volume)
                        goto LOOPEND;
                    else
                        break;
                }
            }
        }
        LOOPEND:

        cout << "=======================INSIDE===========================================" << endl;
        cout << NewVolume << endl << endl;
        it = SortedItems.begin();
        while(it != SortedItems.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }
        cout << "=======================OUTSIDE===========================================" << endl;
        it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }


}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34991356
sergiobg57:

Wow!!!!   That solution is superb!!!!  

As far as I can tell, it is completely dynamic... SMILE!!!

Would you be willing to provide me a few comments on some on some of these lines of code?   I'd like to make sure I fully understand how and what it is doing.

Again, thousand thanks!!!
0
 

Author Comment

by:ExpExchHelp
ID: 34991373
Final question:

Just like in "Step 3", I'd like to provide an update knapsack inventory once the items have been swapped.

How do I compute values for "Total Value", "Total Volume", "Total Weight", "Volume Used", "Volume Left", etc.

Again, below is the code that I used in step 3... step 4 will show me the items... step 5 will be become the new inventory summary.

Again, thank you!!!
std::cout << "Step 5: New 'Knapsack 'Inventory' (using Local Search):" << 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;

Open in new window

0
Highfive Gives IT Their Time Back

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!

 

Author Comment

by:ExpExchHelp
ID: 34991383
Sorry one more follow-up.... I just noticed the "UsedVolume" variable... so, I will be able to compute that.

Not sure about the "Total Value" just yet.

One more important thing.   In this data set, the "bottle neck" was "volume".   It could be though that the bottleneck will be "weight".    So my question...

How can I make sure that both constraints -- volume AND weight -- are taken in consideration for "swapping" items?

EEH
0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34991397
I've done it with haste.
Somethings can be improved, like that part of the code that shows the items inside and outside the knapstack.

Anyway, you might be confused with the STL methods which are pretty simple by the way.
for(int i = 0; i < SortedItems.size();i++){
            for(int c = 0; c<Left_Behind.size();c++){

Open in new window


This is just the looping structure which iterates for every single element inside or outside the backback.
i is the index for inside and c the index for outside items.

  NewVolume = (UsedVolume - SortedItems[i].Volume) + Left_Behind[c].Volume;
                if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){

Open in new window


This calculates if the current used volume can be improved by taking off the current knapsack item(SortedItems[ i ]) and adding the current out of snapsack item(Left_Behind[c])

If it does:

Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedVolume = NewVolume;

Open in new window


Swap items.
The current inside the knapsack item by the current outside the knapsack item.
This swap is performed adding the items to the end of the deque's queue .
This will allow the algorithm to analyze the new added item as well.

if(NewVolume == knapSack_Max_Volume)
                        goto LOOPEND;
                    else
                        break;

Open in new window


Checks to see if the new uptodate volume is the optimal solutioin.
If it is, finish the optimization.
if it doesn't, goes on.
for(int i = 0; i < SortedItems.size();i++){
            for(int c = 0; c<Left_Behind.size();c++){
                NewVolume = (UsedVolume - SortedItems[i].Volume) + Left_Behind[c].Volume;
                if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){

                    Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedVolume = NewVolume;



                    if(NewVolume == knapSack_Max_Volume)
                        goto LOOPEND;
                    else
                        break;
                }
            }
        }
        LOOPEND:

Open in new window

0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34991428
Every (*it), is a knapsack_Item.
The definition of that structure is as follows:
struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

Open in new window



So, if you are doing
(*it).Volume

Open in new window


you can also do:
(*it).Weight;
(*it).Value;
(*it).Index;

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34991482
Again, thanks for providing superb help on this...

I just noticed your recent posts... I'll look at them in a moment.

Meanwhile, I've tried to implement the 2nd constraint for weight.   The full code is shown below.   There are only two things missing (as far as I can tell):

1. I need to compute the new Total Value (1980 vs. 1805).

2. Per the two snapshots, something doesn't "add up" for the weight.   If I compare my XLS output (from Solver), the remaining weight should be 855.    That makes sense... I subtract "25" weight units (item #7) from 680.   Then I add 200 weight units (item #10) to that... giving me 855.

Right now, based on the code that I added (I copied the format/structure from volume), I compute it as "380"... obviously, that's wrong.

Once I get the correct weight summary and the new total value, I'll be in great shape!!  SMILE
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#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) ******



struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

deque<knapsack_Item> SortedItems;
deque<knapsack_Item> Left_Behind;

// Declarations of independent functions
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);


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

int volumeLeft = MAXVOLUME;
int weightLeft = MAXWEIGHT;


// 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 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;
        knapsack_Item kI;
        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)) {

                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    SortedItems.push_back(kI);

                        // 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]];
                }
                else{
                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    Left_Behind.push_back(kI);
                }
                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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

        std::cout << endl;
        std::cout << "Step 4: The newly selected knapsack items (using Local Search) are as follows:" << std::endl;
        std::cout << "==============================================================================" << std::endl << endl;
		
        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            //cout << "Item: "   << (*it).Index  << endl;
            //cout << "Weight: " << (*it).Weight << endl;
            //cout << "Value: "  << (*it).Value  << endl;
            //cout << "Volume: " << (*it).Volume << endl;
            //cout << endl << endl;
            it++;
        }
        //cout << "==================================================================" << endl;
        
		it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            //cout << "Item: "   << (*it).Index  << endl;
            //cout << "Weight: " << (*it).Weight << endl;
            //cout << "Value: "  << (*it).Value  << endl;
            //cout << "Volume: " << (*it).Volume << endl;
            //cout << endl << endl;
            it++;
        }
        
		unsigned int UsedVolume = knapSack_Max_Volume - volumeLeft;
        unsigned int NewVolume = 0x0;

		unsigned int UsedWeight = knapSack_Max_Weight - weightLeft;
        unsigned int NewWeight = 0x0;
		
        
		for(int i = 0; i < SortedItems.size();i++){
           
			for(int c = 0; c<Left_Behind.size();c++){
                NewVolume = (UsedVolume - SortedItems[i].Volume) + Left_Behind[c].Volume;
                if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){

                    Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedVolume = NewVolume;
					
                    if(NewVolume == knapSack_Max_Volume)
                        goto LOOPEND;
                    else
                        break;
                }
            }


            for(int c = 0; c<Left_Behind.size();c++){
                NewWeight = (UsedWeight - SortedItems[i].Weight) + Left_Behind[c].Weight;
                if((UsedWeight < NewWeight) && (NewWeight <= knapSack_Max_Weight)){

                    Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedWeight = NewWeight;

					if(NewWeight == knapSack_Max_Weight)
                        goto LOOPEND;
                    else
                        break;
                }
            }
        }
		LOOPEND:
		
        it = SortedItems.begin();
        while(it != SortedItems.end()){

            std::cout << "Item# " << setw (2) << (*it).Index << "  --  Value: " << setw (3) << (*it).Value << "   Volume: " << setw (3) << (*it).Volume << "   Weight: " << setw (3) << (*it).Weight << std::endl;
            it++;
        }

        // Console output providing the new knapsack's inventory (including "Total Value" of the items; total volume/weight of the items).
        std::cout << endl << endl << endl;
        std::cout << "Step 5: New 'Knapsack 'Inventory' (using Local Search):" << 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) << UsedVolume << std::endl;
        std::cout << "Volume Capacity (left):   " << setw (4) << knapSack_Max_Volume - UsedVolume << std::endl;
        std::cout << endl;
        std::cout << "Total Weight (available): " << setw (4) << knapSack_Max_Weight << std::endl;
        std::cout << "Total Weight (used):      " << setw (4) << UsedWeight - weightLeft << std::endl;
        std::cout << "Weight Capacity (left):   " << setw (4) << knapSack_Max_Weight - UsedWeight << std::endl;
        std::cout << endl << endl << endl;
}

Open in new window

Snapshot.jpg
NewInventory.jpg
0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34991634
You've included a new loop for selection which you'll deform the knapsack.
If you wanna weight to be taken in account, you must do like this..
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#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) ******



struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

deque<knapsack_Item> SortedItems;
deque<knapsack_Item> Left_Behind;

// Declarations of independent functions
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);


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

int volumeLeft = MAXVOLUME;
int weightLeft = MAXWEIGHT;


// 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 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;
        knapsack_Item kI;
        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)) {

                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    SortedItems.push_back(kI);

                        // 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]];
                }
                else{
                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    Left_Behind.push_back(kI);
                }
                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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

        std::cout << endl;
        std::cout << "Step 4: The newly selected knapsack items (using Local Search) are as follows:" << std::endl;
        std::cout << "==============================================================================" << std::endl << endl;

        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            //cout << "Item: "   << (*it).Index  << endl;
            //cout << "Weight: " << (*it).Weight << endl;
            //cout << "Value: "  << (*it).Value  << endl;
            //cout << "Volume: " << (*it).Volume << endl;
            //cout << endl << endl;
            it++;
        }
        //cout << "==================================================================" << endl;

		it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            //cout << "Item: "   << (*it).Index  << endl;
            //cout << "Weight: " << (*it).Weight << endl;
            //cout << "Value: "  << (*it).Value  << endl;
            //cout << "Volume: " << (*it).Volume << endl;
            //cout << endl << endl;
            it++;
        }

		unsigned int UsedVolume = knapSack_Max_Volume - volumeLeft;
        unsigned int NewVolume = 0x0;

		unsigned int UsedWeight = knapSack_Max_Weight - weightLeft;
        unsigned int NewWeight = 0x0;


		for(int i = 0; i < SortedItems.size();i++){

			for(int c = 0; c<Left_Behind.size();c++){
                NewVolume = UsedVolume - SortedItems[i].Volume + Left_Behind[c].Volume;
                if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){
                    NewWeight = UsedWeight - SortedItems[i].Weight + Left_Behind[c].Weight;
                    if(NewWeight > knapSack_Max_Weight)
                        break;
                    UsedWeight = NewWeight;
                    Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedVolume = NewVolume;

                    if(NewVolume == knapSack_Max_Volume)
                        goto LOOPEND;
                    else
                        break;
                }
            }

        }
		LOOPEND:

        it = SortedItems.begin();
        while(it != SortedItems.end()){

            std::cout << "Item# " << setw (2) << (*it).Index << "  --  Value: " << setw (3) << (*it).Value << "   Volume: " << setw (3) << (*it).Volume << "   Weight: " << setw (3) << (*it).Weight << std::endl;
            it++;
        }

        // Console output providing the new knapsack's inventory (including "Total Value" of the items; total volume/weight of the items).
        std::cout << endl << endl << endl;
        std::cout << "Step 5: New 'Knapsack 'Inventory' (using Local Search):" << 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) << UsedVolume << std::endl;
        std::cout << "Volume Capacity (left):   " << setw (4) << knapSack_Max_Volume - UsedVolume << std::endl;
        std::cout << endl;
        std::cout << "Total Weight (available): " << setw (4) << knapSack_Max_Weight << std::endl;
        std::cout << "Total Weight (used):      " << setw (4) << UsedWeight << std::endl;
        std::cout << "Weight Capacity (left):   " << setw (4) << knapSack_Max_Weight - UsedWeight << std::endl;
        std::cout << endl << endl << endl;
}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34991684
Wow!!!   That is awesome!!!    SMILE... GRIN!!!

Ok, here's the "final final" question (I hope).

How can I compute the total value for the new process.    Currently, I'm still using the variable 'totalValue' from the Greedy algorithm... that was is 1,805.    As you know, the new total value must equal 1980.

Again, I truly appreciate your help on this!!!

EEH
0
 
LVL 3

Accepted Solution

by:
sergiobg57 earned 500 total points
ID: 34991720
The code is so messy that i didn't want to add more code into the algorithm.
So i created a new function to calculate it.

But i do recommend you to study OOP(object oriented programming) and STL.
For this software it's not needed as it's academic.(teachers have to deal with it)
But for a real software, OOP would greatly enhance your code readability.
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#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) ******



struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

deque<knapsack_Item> SortedItems;
deque<knapsack_Item> Left_Behind;

// Declarations of independent functions
unsigned int GetTotalValue();
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);


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

int volumeLeft = MAXVOLUME;


// 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 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;
        knapsack_Item kI;
        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)) {

                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    SortedItems.push_back(kI);

                        // 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]];
                }
                else{
                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    Left_Behind.push_back(kI);
                }
                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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

        int i, j;

        cout << "****************************************************" << endl << endl;
        cout << "Testing Value Passing (from Greedy function to Local Search function):" << endl;

        cout << "Total Value: " << totalValue << endl << endl;

        cout << "Max Volume: "  << knapSack_Max_Volume << endl;
        cout << "Volume Used: " << knapSack_Max_Volume - volumeLeft << endl;
        cout << "Volume Left: " << volumeLeft << endl << endl;

        cout << "Max Weight: "  << knapSack_Max_Weight << endl;
        cout << "Weight Used: " << knapSack_Max_Weight - weightLeft << endl;
        cout << "Weight Left: " << weightLeft << endl << endl;

        for (int i = 0; i < linecount; i++)
                cout << SortedRatios[i] << endl;
                cout << endl;

        for (int i = 0; i < linecount; i++)
                cout << setw (3) << Ratios[i] << endl;
                cout << endl;



        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }
        cout << "==================================================================" << endl;
        it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }
        unsigned int UsedVolume = knapSack_Max_Volume - volumeLeft;
        unsigned int NewVolume = 0x0;
        for(int i = 0; i < SortedItems.size();i++){
            for(int c = 0; c<Left_Behind.size();c++){
                NewVolume = (UsedVolume - SortedItems[i].Volume) + Left_Behind[c].Volume;
                if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){

                    Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedVolume = NewVolume;



                    if(NewVolume == knapSack_Max_Volume)
                        goto LOOPEND;
                    else
                        break;
                }
            }
        }
        LOOPEND:

        cout << "=======================INSIDE===========================================" << endl;
        cout << NewVolume << endl << endl;
        it = SortedItems.begin();
        while(it != SortedItems.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }
        cout << "=======================OUTSIDE===========================================" << endl;
        it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            cout << "Item: "   << (*it).Index  << endl;
            cout << "Weight: " << (*it).Weight << endl;
            cout << "Value: "  << (*it).Value  << endl;
            cout << "Volume: " << (*it).Volume << endl;
            cout << endl << endl;
            it++;
        }

        cout << "Value >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << GetTotalValue() << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<" << endl;
}

unsigned int GetTotalValue(){

    unsigned int ret = 0;

    deque<knapsack_Item>::iterator it = SortedItems.begin();
    while (it != SortedItems.end()){
        ret += (*it).Value;
        it++;
    }
    return ret;

}

Open in new window

0
 

Author Comment

by:ExpExchHelp
ID: 34991765
sergiobg57:

Once I merged the two different code version (based on the previous console output from posting http::#34991634, I get some awkward looking Total Value... pls see snapshot below.

How can I maintain the code from http::#34991634 but using the new function for total value.

Once I got this, I will close the question for sure.  

EEH
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#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) ******



struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

deque<knapsack_Item> SortedItems;
deque<knapsack_Item> Left_Behind;

// Declarations of independent functions
unsigned int GetTotalValue();
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);



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

int volumeLeft = MAXVOLUME;
int weightLeft = MAXWEIGHT;


// 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 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;
        knapsack_Item kI;
        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)) {

                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    SortedItems.push_back(kI);

                        // 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]];
                }
                else{
                    kI.Volume = itemVolume[SortedRatios[i]];
                    kI.Value = itemValue[SortedRatios[i]];
                    kI.Index = SortedRatios[i] + 1;
                    kI.Weight = itemWeight[SortedRatios[i]];
                    Left_Behind.push_back(kI);
                }
                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
    knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);
}


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

        std::cout << endl;
        std::cout << "Step 4: The newly selected knapsack items (using Local Search) are as follows:" << std::endl;
        std::cout << "==============================================================================" << std::endl << endl;

        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){

            //cout << "Item: "   << (*it).Index  << endl;
            //cout << "Weight: " << (*it).Weight << endl;
            //cout << "Value: "  << (*it).Value  << endl;
            //cout << "Volume: " << (*it).Volume << endl;
            //cout << endl << endl;
            it++;
        }
        //cout << "==================================================================" << endl;

		it = Left_Behind.begin();
        while(it != Left_Behind.end()){

            //cout << "Item: "   << (*it).Index  << endl;
            //cout << "Weight: " << (*it).Weight << endl;
            //cout << "Value: "  << (*it).Value  << endl;
            //cout << "Volume: " << (*it).Volume << endl;
            //cout << endl << endl;
            it++;
        }

		unsigned int UsedVolume = knapSack_Max_Volume - volumeLeft;
        unsigned int NewVolume = 0x0;

		unsigned int UsedWeight = knapSack_Max_Weight - weightLeft;
        unsigned int NewWeight = 0x0;


		for(int i = 0; i < SortedItems.size();i++){

			for(int c = 0; c<Left_Behind.size();c++){
                NewVolume = UsedVolume - SortedItems[i].Volume + Left_Behind[c].Volume;
                if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){
                    NewWeight = UsedWeight - SortedItems[i].Weight + Left_Behind[c].Weight;
                    if(NewWeight > knapSack_Max_Weight)
                        break;
                    UsedWeight = NewWeight;
                    Left_Behind.push_back(SortedItems[i]);
                    SortedItems.erase(SortedItems.begin()+i);
                    SortedItems.push_back(Left_Behind[c]);
                    Left_Behind.erase(Left_Behind.begin()+c);
                    UsedVolume = NewVolume;

                    if(NewVolume == knapSack_Max_Volume)
                        goto LOOPEND;
                    else
                        break;
                }
            }

        }
		LOOPEND:

        it = SortedItems.begin();
        while(it != SortedItems.end()){

            std::cout << "Item# " << setw (2) << (*it).Index << "  --  Value: " << setw (3) << (*it).Value << "   Volume: " << setw (3) << (*it).Volume << "   Weight: " << setw (3) << (*it).Weight << std::endl;
            it++;
        }

        // Console output providing the new knapsack's inventory (including "Total Value" of the items; total volume/weight of the items).
        std::cout << endl << endl << endl;
        std::cout << "Step 5: New 'Knapsack 'Inventory' (using Local Search):" << std::endl;
        std::cout << "======================================================" << std::endl << endl;
        std::cout << "Total Knapsack Value:     " << setw (3) << GetTotalValue << std::endl;
        std::cout << endl;
        std::cout << "Total Volume (available): " << setw (4) << knapSack_Max_Volume << std::endl;
        std::cout << "Total Volume (used):      " << setw (4) << UsedVolume << std::endl;
        std::cout << "Volume Capacity (left):   " << setw (4) << knapSack_Max_Volume - UsedVolume << std::endl;
        std::cout << endl;
        std::cout << "Total Weight (available): " << setw (4) << knapSack_Max_Weight << std::endl;
        std::cout << "Total Weight (used):      " << setw (4) << UsedWeight << std::endl;
        std::cout << "Weight Capacity (left):   " << setw (4) << knapSack_Max_Weight - UsedWeight << std::endl;
        std::cout << endl << endl << endl;
}

unsigned int GetTotalValue(){

    unsigned int ret = 0;

    deque<knapsack_Item>::iterator it = SortedItems.begin();
    while (it != SortedItems.end()){
        ret += (*it).Value;
        it++;
    }
    return ret;
}

Open in new window

NewTotalValue.jpg
0
 

Author Comment

by:ExpExchHelp
ID: 34991844
sergiobg57:

Never mind the last question... I forgot to add the "()" for the GetValue function cout statement.

It's perfect now!!!

Again, I truly appreciate your support in this matter.    Experts like you make this forum absolutely the best site on the web.

EEH
std::cout << "Total Knapsack Value:     " << setw (3) << GetTotalValue() << std::endl;

Open in new window

0
 

Author Closing Comment

by:ExpExchHelp
ID: 34991846
Great solution!!!
0
 
LVL 3

Expert Comment

by:sergiobg57
ID: 34991894
Thanks. =)
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
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…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

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

22 Experts available now in Live!

Get 1:1 Help Now