This course will introduce you to C++ 11 and teach you about syntax fundamentals.

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

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;
}
```

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

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

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

http://en.wikipedia.org/wiki/Greedy_algorithm

http://en.wikipedia.org/wiki/Local_search_(optimization)

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

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

```
// 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?

Sara

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

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.