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 weightint 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 functionsvoid 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;}

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

>>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")

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).

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

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

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?

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

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

EEH

0

Featured Post

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Calculating holidays and working days is a function that is often needed yet it is not one found within the Framework. This article presents one approach to building a working-day calculator for use in .NET.

It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…

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.