I'm going through a learning curve with C++... specifically as it pertains passing pointers, variables, etc. from one function to another.

Please see code below. The program executes successfully and generates the desired outcome based on function "knapsack_Greedy_Algorithm".

Now, I'd like to modify the program via adding a 2nd function "knapsack_LocalSearch_Algorithm" (see bottom of code).

Based on what was computed in the "Greedy" algorithm, I want to pass the following from "Greedy" to "LocalSearch":
- which items are in the knapsack
- which items are NOT in the knapsack
- the computed values for volume used, volume left, weight used, weight left, etc.

For testing purposes, I've copied the while loop from the Greedy and inserted it into the Local Search. I then added a simple cout statement "This is a test!".

Right now, the cout statement "This is a test!" does not print to the console. So, I'm sure I have either not passed the variables properly and my syntax is incorrect (even though the program compiles).

My question: How do I modify the code for LocalSearch (function call) so that I can re-utilize the previously computed values?

Thanks,
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 selectionint itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Knapsack items' array specifing their valueint itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Knapsack items' array specifing their volumeint 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 1100int knapSack_Max_Volume = 1100;#define MAXWEIGHT 1400int 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 1900int knapSack_Max_Volume = 1900;#define MAXWEIGHT 1700int 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 functionsvoid knapsack_Greedy_Algorithm();// Structure used in the knapsack problemtypedef 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;}void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft) { int i, j; 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 << "This is a test!"; } i++; }}

You're right... I missed that step... I've added code to lines:

- 54
- 177

Obviously, that didn't do it as I still don't show the test message. What am I missing? Do I need to include all the variable names in the parenthesis? If yes, did I do it correctly?

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 selectionint itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Knapsack items' array specifing their valueint itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Knapsack items' array specifing their volumeint 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 1100int knapSack_Max_Volume = 1100;#define MAXWEIGHT 1400int 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 1900int knapSack_Max_Volume = 1900;#define MAXWEIGHT 1700int 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 functionsvoid knapsack_Greedy_Algorithm();void knapsack_LocalSearch_Algorithm();// Structure used in the knapsack problemtypedef 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 void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft); }void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft) { int i, j; 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 << "This is a test!"; } i++; }}

You need to include the type list in the declaration on line 54. The variable names themselves are optional, but I prefer to leave them in as it makes it clearer what the function does. eg.

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

I just tested your code, and you won't see the message printed if the knapsack is already full i.e. if weightLeft or volumeLeft has already reached 0 (which they are with your current test data), as the while loop condition is false to start with.

Is the local search algorithm meant to be a second-stage in the process, following on from the greedy search, or are they meant to be 2 separate algorithms to solve the same problem?

And, yes, you're right... for this data set, the volume/weight will be 0. Therefore, for testing purposes, I changed the while loop as shown below. Still, it doesn't print the statement.

What else am I overlooking?

EEH

P.S. Yes, the "LocalSearch" is a continuation of the Greedy. Depending on the data set, I will or will not hit the optimal solution with the Greedy algorithm alone. I'm trying to now look into some methods where I swap items.

For instance, I might create a more optimal "total value" by taking out 1 item from the knapsack and replace it with another item. For this process, I simply want to make all previously computed information "available" in the LocalSearch.

Assuming the test msg will print, will this work by passing on the last recent computed value (weights used, weights left, etc.)?

A single equals sign means assignment, even in a while or if condition test. So you are actually assigning 0 to weightLeft and volumeLeft with your change, not testing if it equals 0. And when removing the (i < linecount) condition, the program crashes, as it attempts to access outside the bounds of the SortedRatios array in the if statement.

If you just want to test the passing of the arguments, for now just add a section at the start of the function that outputs the arguments. Eg.

Great... that'll work for me. Thanks for the good advice. Looks like everything is passed properly.

Just to be certain though... I don't have to be concerned about having "lost" pointers reference, etc? Essentially, based on statement below (code section), am I passing all information from Greedy to LocalSearch?

EEH

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

In fact, as you're still learning C++, I'd suggest you avoid the complexity of pointers and dynamic memory management unless you really need to use them, which you actually don't for the code you've provided above. To avoid the need for pointers, firstly change linecount to be a constant eg:

I changed it to be all capitals, as that's fairly typical programming practice, though not necessary, so you don't have to do that if you don't want. Others prefer just to put a 'k' at the start of the variable name to indicate that it's constant. If you change the name, you would of course have to change it all throughout the code as well.

Then you can simply use arrays. Eg. in greedy function:

int SortedRatios[LINE_COUNT];float Ratios[LINE_COUNT];

at the bottom of knapsack_Greedy_Algorithm (and the same for Ratios). Just make sure you don't delete them before passing them to the local algorithm, do it after.

0

Featured Post

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

What is C++ STL?:
STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector.
…

Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …

The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.