Solved

Working program... need some help with explanation

Posted on 2011-03-13
7
435 Views
Last Modified: 2012-05-11
I have a working C++ program that selects items (based on available weight volume/weight limits).   The program is based on the "knapsack" concept.

Again, the program itself works fine and doesn't require any modification whatsoever.

However, I'm trying to better understand the program (as I received some help in this forum) and some of the methods.   I've posted the code below.

So, what I'm interested in is to obtain some comments/feedback on how some of the stuff works.   More specifically, I'm particularly keen on getting info/comments on the following lines... what do they "do"?

- 46, 47 ("deque")
- 131 ("SortedItems.push_back")
- 189 ("iterator")
- 194 ("it = Left_Behind.begin();")
- 208:229 .... how does the whole function work?
- 268 ("iterator")

The above section covers the primary topics/concepts that I'm not entirely following.    PARTICULARLY the ForLoop in lines 208 to 229.

If someone could add comments and re-post the code, I'd truly appreciate it!

Thanks,
EEH



// 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
#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};			


// 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:
        knapsack_Greedy_Algorithm();

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


void knapsack_Greedy_Algorithm() {

        // 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 (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]] << "   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' (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 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;
		

        // 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()){
            it++;
        }

		it = Left_Behind.begin();
        while(it != Left_Behind.end()){
            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 << "   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: 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 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;

        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

0
Comment
Question by:ExpExchHelp
7 Comments
 
LVL 11

Assisted Solution

by:DeepuAbrahamK
DeepuAbrahamK earned 100 total points
ID: 35122575
>>So, what I'm interested in what be someone providing me some comments on how some of the stuff works.   More specifically, I'm particularly keen on >>getting info/comments on the following lines... what do they "do"?

>>- 46, 47 ("deque")
>>- 131 ("SortedItems.push_back")
>>- 189 ("iterator")
>>- 194 ("it = Left_Behind.begin();")
>>- 208:229 .... how does the whole function work?
>>- 268 ("iterator")

Most of these are based on stl "Standard template library"
deque ------>Double ended queue ----> http://www.cplusplus.com/reference/stl/deque/
SortedItems.push_back------->SortedItems is an object of  deque ------>http://www.cplusplus.com/reference/stl/deque/push_back/
iterator--------->http://www.cplusplus.com/reference/stl/deque/begin/
it = Left_Behind.begin(); -------> iterator object it is getting the fist item in the deque

re 208:229.. it is just adding/erasing the deque here
0
 

Author Comment

by:ExpExchHelp
ID: 35122658
DeepuAbrahamK:

I've googled some of this stuff before... appreciate the references... I'll look at them again.

I'll be more than happy to award you the points; however, I'd like to get more info on lines 208:229.   In general I know that's adding/deleting items but I don't follow all of the logic.

If you can please provide additional comments to each line in the If statement (starting at 211).

Thanks,
EEH
0
 
LVL 11

Expert Comment

by:DeepuAbrahamK
ID: 35126807
0
IT, Stop Being Called Into Every Meeting

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

 

Author Comment

by:ExpExchHelp
ID: 35127394
DeepuAbrahamK:

I know these sites... and I know how they work conceptually.

The question remains, I'd like to understand the ForLoop (lines 208:229).
0
 
LVL 32

Expert Comment

by:sarabande
ID: 35128719
the comment at top of the function pretty well describes what the sequence you were asking for is doing:

        // 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.
        // ************************************************************************************************

Open in new window


it isn't an easy job to comment each line of a foreign code beside of only telling syntax or tech issues.

i made the experience that writing new code for an algorithm which is mathematically clear is much easier than trying to totally understand uncommented code made by others which may or may not implement an algorithm rightly. can't you ask where you got the code?

Sara

0
 
LVL 8

Accepted Solution

by:
ssnkumar earned 400 total points
ID: 35133952
> 208:229 .... how does the whole function work?
Here you are having for loop inside a for loop.
The first loop checks if all the SortedItems->size() are done.
The 2nd loop checks the LeftBehind->size().
It finds the NewVolume and NewWeight.
If NewWeight is greater than the KnapSack_Max_Weight, it just comes out of the 2nd loop and goes for the next item in the first loop.
If not, then it pushes the current item from SortedItems into LeftBehind and removes the item from SortedItems.
And pushes the LeftBehind Item to SortedItems and removes it from the LeftBehind items.
0
 

Author Closing Comment

by:ExpExchHelp
ID: 35143545
ssnkumar

Thanks for the explanation on the ForLoop... that's what I was most interested in.

EEH
0

Featured Post

IT, Stop Being Called Into Every Meeting

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

Join & Write a Comment

Suggested Solutions

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
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 additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

706 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