Solved

C++ -- Modification of Function

Posted on 2011-03-25
6
457 Views
Last Modified: 2012-06-27
I have a C++ solution that may require some tweaking.

The code originated out of a (somewhat) long thread.   If anyone cares for all of the details, you can find them at:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_26834581.html#a35216383

Be aware might it would take a moment to digist the information.   Instead, allow me to recap the problem/solution and then explain what might require some tweaking:

o The program solves the "knapsack" (spatial optimization) problem.
o The code executes fine.   Right now, it contains five (5) data sets.   The first (original) data set provides a solution that fully meets the requirements.
o That is, the "Greedy Algorithm" first determines the total value ... being outputted to the console in "Step 3".
o Depending on the data set, the "Greedy" algorithm may not necessarily provide the most optimal ouput.   This is where the "Local Search" algorithm comes in.
o Essentially, it "looks" at items that were not picked in the Greedy and compares them with items in the knapsack.  
o As part of the optimization process, it checks if removing a selected item (thereby freeing up volume/weight capacity) would allow an non-selected, higher value-item to be placed into the knapsack.
o Again, per the original data set, the "Local Search" actually improved the total value by 175 total value units (see step 5 of the code... or better see JPG "OriginalDataSet.jpg").

Now, here's what I need some help with:
o Apparently, the Local Search algorithm does >> NOT << always find an improved/equal solution (when compared to the Greedy).  
o As a matter of fact, out of the four new data sets, three (3) produce a worse solution.  
o That is, data set [1, 2, 4] result in solution that provides a smaller total value.

My question:

How should the Local Search function be modified in order to ensure either the same (or hopefully) better output in step #5?

Thanks,
EEH

P.S.  The 2nd JPG (Data Set 1) shows a "weird" value in the last line of the console output.   That's because the total value in the Greedy is larger than the total value in the Local Search.   I've actually modified the code by simple adding an IF-ELSE statement in the Step 5 console output.   Unfortunately, I don't have access to the modified code.    Simply put, if the total value oof LocalSearch is greater then I print:   LocalSearchTotal - GreedyTotal... else, I print GreedyTotal - LocalSearchTotal.   [Pseudocode]
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <deque>
#include <math.h>
#include <limits.h>
using namespace std;

// Declaration of variables


// ****** Begin of ORIGINAL DATA ******
#define MAXWEIGHT 1400																		// Testing Data (for Local Search)
int knapSack_Max_Weight = 1400;																// Testing Data (for Local Search)

#define MAXVOLUME 1100																		// Testing Data (for Local Search)
int knapSack_Max_Volume = 1100;																// Testing Data (for Local Search)
								
int linecount = 13;																			// Testing Data (for Local Search)
int itemValue[13]  = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50};		// Testing Data (for Local Search)
int itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200};		// Testing Data (for Local Search)
int itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200};		// Testing Data (for Local Search)
// ****** End of ORIGINAL DATA ******




// ****** Begin of 1st Data Set (10 items) ******
//#define MAXWEIGHT 1200															// Knapsack's maximum weight (constant)
//int knapSack_Max_Weight = 1200;													// Knapsack's maximum weight 
//
//#define MAXVOLUME 1000															// Knapsack's maximum volume (constant)										
//int knapSack_Max_Volume = 1000;													// Knapsack's maximum volume 
//									
//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 itemWeight[10] = {100, 200, 450, 200, 65, 200, 200, 350, 300, 478};			// Knapsack items' array specifing their weight
//int itemVolume[10] = {120, 200, 200, 130, 175, 200, 200, 285, 400, 422};		// Knapsack items' array specifing their volume
// ****** End of of 1st Data Set (10 items) ******


// ****** Begin of 2nd Data Set (12 items) ******
/*#define MAXWEIGHT 1350																		
int knapSack_Max_Weight = 1350;	

#define MAXVOLUME 1150																		
int knapSack_Max_Volume = 1150;																
								
int linecount = 12;																			
int itemValue[12]  = {35, 200, 400, 300, 555, 250, 75, 122, 680, 500, 125, 275};
int itemWeight[12] = {75, 215, 333, 350, 375, 100, 75, 80, 410, 175, 100, 175};	
int itemVolume[12] = {90, 222, 240, 300, 400, 177, 75, 110, 150, 350, 74, 100};	*/			
// ****** End of of 2nd Data Set (12 items) ******


// ****** Begin of 3rd Data Set (15 items) ******
/*#define MAXWEIGHT 1850																		
int knapSack_Max_Weight = 1850;

#define MAXVOLUME 2100																		
int knapSack_Max_Volume = 2100;																
									
int linecount = 15;																			
int itemValue[15]  = {200, 180, 200, 200, 200, 300, 333, 300, 515, 300, 500, 600, 900, 700, 600};
int itemWeight[15] = {150, 121, 155, 350, 50, 100, 177, 250, 420, 175, 175, 175, 575, 565, 600};
int itemVolume[15] = {120, 170, 130, 228, 55, 130, 250, 150, 288, 100, 100, 100, 700, 725, 440};*/				
// ****** End of of 3rd Data Set (15 items) ******


// ****** Begin of 4th Data Set (20 items) ******
/*#define MAXWEIGHT 3000																		
int knapSack_Max_Weight = 3000;

#define MAXVOLUME 2875																		
int knapSack_Max_Volume = 2875;																
											
int linecount = 20;																			
int itemValue[20]  = {200, 200, 200, 200, 200, 300, 300, 300, 300, 300, 500, 600, 900, 700, 600, 250, 500, 430, 95, 250};	
int itemWeight[20] = {100, 200, 150, 350, 50, 100, 200, 250, 50, 175, 175, 175, 575, 565, 600, 175, 250, 220, 25, 120};	
int itemVolume[20] = {120, 200, 130, 300, 50, 120, 250, 150, 150, 100, 100, 100, 700, 725, 440, 175, 350, 320, 35, 140};	*/			
// ****** End of of 4th Data Set (20 items) ******



// Declaration of slack variables for volume and weight
int volumeLeft = MAXVOLUME;
int weightLeft = MAXWEIGHT;

// Structure used in the knapsack problem (for Greedy Algorithm)
typedef struct PossibleMatch {
        int nItem;
        int nValue;
        int nVolume;
        int nWeight;
}  ;

// Structure used in the knapsack problem (for Local Search Algorithm)
struct knapsack_Item{
    unsigned int Index;
    unsigned int Value;
    unsigned int Volume;
    unsigned int Weight;
};

// Declarations of "double-ended queues" (sequence containers)
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);
unsigned int GetNewTotalValue_LocalSearch();




// 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) << "Weight: " << setw (3) << itemWeight[SortedRatios[i]]  << setw (11) << "Volume: " << setw (3) << itemVolume[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 (Greedy Algorithm):" << 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]] << "   Weight: " << setw (3) << itemWeight[SortedRatios[i]] << "   Volume: " << setw (3) << itemVolume[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' (Greedy Algorithm):" << std::endl;
        std::cout << "================================================" << std::endl << endl;
        std::cout << "Total Knapsack Value:     " << setw (3) << totalValue << 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;
		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 << 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) {
        // ********************** General Summary of the implemented Local Search Algorithm *********************
        // This function will add items into a knapsack using a "local search" algorithm.
        // This algorithm determines what items are "left behind".   
		// Based on the calculated "slack" (both for volume and weight), the algorithm determines if swapping items will have a
		// beneficial impact on the knapsack's total value.
		// In other words, by removing an initially selected item and removing it, additional space (both volume and weight)
		// is freed up.  Now, potentially, another larger item with (potentially) a greter total value can fit in the knapsack.
		// In the end, this swapping of item may yield an additional net gain for the total value.
		// This local search algorithm has been tested on the 2nd data set and did provide a net gain of 175 total value units.
		// This gain of 175 value points matches MS-Solver's solution; therefore, providing the optimal value to the user.
		// However, depending on the data set, it is not guaranteed that this algorithm will always find the optimal solution.
        // ************************************************************************************************
		
        std::cout << endl;
        std::cout << "Step 4: The selected knapsack items are as follows (Local Search Algorithm):" << std::endl;
        std::cout << "============================================================================" << std::endl << endl;

        deque<knapsack_Item>::iterator it = SortedItems.begin();
        while(it != SortedItems.end()){
            // cout << "Item: "   << (*it).Index  << endl;					// Output testing (console output is done via the ForLoop below)
            // cout << "Value: "  << (*it).Value  << endl;					// Output testing (console output is done via the ForLoop below)
			// cout << "Volume: " << (*it).Volume << endl;					// Output testing (console output is done via the ForLoop below)           
			// cout << "Weight: " << (*it).Weight << endl;					// Output testing (console output is done via the ForLoop below)
            // cout << endl << endl;
            it++;
        }

		it = Left_Behind.begin();
        while(it != Left_Behind.end()){
            // cout << "Item: "   << (*it).Index  << endl;					// Output testing (console output is done via the ForLoop below)
            // cout << "Value: "  << (*it).Value  << endl;					// Output testing (console output is done via the ForLoop below)
			// cout << "Volume: " << (*it).Volume << endl;					// Output testing (console output is done via the ForLoop below)           
			// cout << "Weight: " << (*it).Weight << endl;					// Output testing (console output is done via the ForLoop below)
            // cout << endl << endl;
            it++;
        }

		// Declaration of the unused (slack) for volume
		unsigned int UsedVolume = knapSack_Max_Volume - volumeLeft;
        unsigned int NewVolume = 0x0;

		// Declaration of the unused (slack) for weight
		unsigned int UsedWeight = knapSack_Max_Weight - weightLeft;
        unsigned int NewWeight = 0x0;

		// Determines if swapping of items will provide a net gain for the knapsack's total value
		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:

		// Sort the knapsack items
        it = SortedItems.begin();
        while(it != SortedItems.end()){

            std::cout << "Item# " << setw (2) << (*it).Index << "  --  Value: " << setw (3) << (*it).Value << "   Weight: " << setw (3) << (*it).Weight << "   Volume: " << setw (3) << (*it).Volume << 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: Knapsack 'Inventory' (Local Search Algorithm):" << std::endl;
        std::cout << "======================================================" << std::endl << endl;
        std::cout << "Total Knapsack Value:     " << setw (3) << GetNewTotalValue_LocalSearch() << 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;
        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 << endl;

        std::cout << "Implementing the Local Search algorithm improved the optimal solution by:" << std::endl;
        std::cout << GetNewTotalValue_LocalSearch() - totalValue << " total value units!" << std::endl;
		std::cout << endl << endl;
}


unsigned int GetNewTotalValue_LocalSearch(){
		// ********************** General Summary of the Get Total Value function *********************
		// Given the implementation of the "local search" algorithm, this function was created to keep
		// track of the total new value that is created based on swapping items in/out the knapsack.
		// ********************************************************************************************
		unsigned int ret = 0;

		// Determine the new total value based on the Local Search algorithm
		deque<knapsack_Item>::iterator it = SortedItems.begin();
		while (it != SortedItems.end()){
			ret += (*it).Value;
			it++;
		}
		return ret;
}

Open in new window

OriginalDataSet.jpg
DataSet1.jpg
0
Comment
Question by:ExpExchHelp
  • 3
  • 2
6 Comments
 
LVL 16

Expert Comment

by:imladris
Comment Utility
From a brief look this loop in the local search algorithm:

            for(int i = 0; i < SortedItems.size();i++){
                  for(int c = 0; c<Left_Behind.size();c++){
                                              ...
                     if(NewWeight > knapSack_Max_Weight)
                        break;
                    UsedWeight = NewWeight;
                    ...
                  }


is the heart of it. I note that when considering swaps the only criteria for succes appears to be these lines:

                   if(NewWeight > knapSack_Max_Weight)
                        break;

That is, if the new weight exceeds the knapsack max, then the swap is discarded; otherwise it is made.

Therefore, since the only criteria is that the swap use more of the knapsacks "weight" capacity, this loop is optomizing for weight usage; it is ignoring value. If you want to guarantee that the value does not decrease you will need to specify something about value in the criteria. The simple spec would be to ensure that value of the item being swapped in is not less than the value of the item being replaced.
0
 

Author Comment

by:ExpExchHelp
Comment Utility
imladris:

Thanks for chiming in...  do you have a recommendation for tackling this change?

EEH

0
 
LVL 16

Accepted Solution

by:
imladris earned 500 total points
Comment Utility
Well, I imagine you would add something about value in those lines.

This additional line about NewValue calculates the new value based on the swap, and nixes it if the total value decreases. You would have to prepare the TotalValue variable (probably in the same loop where UsedWeight etc. are calculated) and maintain it as swaps are done. And an additional condition is added to the break line, that breaks if the value decreases.



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;
   --->           NewValue  = TotalValue - SortedItems[i].Value + Left_Behind[c].Value;
                    if(NewWeight > knapSack_Max_Weight || NewValue<TotalValue)
                        break;

Open in new window

0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

Author Comment

by:ExpExchHelp
Comment Utility
imladris:

Thanks for you help... as you suggested, I must somehow (don't know exactly how just yet) modify the code to include the "NewValue" variable.  

Currently, it's underlined... see attached JPG.

I'll look into it tomorrow... hopefully I can figure out how to accommodate the change.   Any thoughts on this are welcome.

EEH
NewValue.jpg
0
 
LVL 1

Expert Comment

by:jefftope
Comment Utility
Hi,
A couple of points;
Firstly crank up your warnings on the compiler and sort out your signed/unsigned issues. for simplicity set everything to signed;  that will sort out your numeric overflow which is why you are getting a "wierd" value.
Secondly change your swaps to std::swap() which will allow you to completely eliminate the tmp1 variable that is used for both floats and int.
Compiler warnings are for a reason!
You might also consider removing a selection of large items and replacing with a selection of small items. i.e. where one(or more) large item blocks the filling with multiple small items.
0
 

Author Comment

by:ExpExchHelp
Comment Utility
jefftope:

Thanks... I'll look into it... but that won't fix the "NewValue" declaration problem, right?

EEH
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

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

743 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

18 Experts available now in Live!

Get 1:1 Help Now