Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.
// 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 selection
int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Knapsack items' array specifing their value
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Knapsack items' array specifing their volume
int 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 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}; */
// ****** End of TESTING DATA (other than the data provided) ******
// ****** Begin of TESTING DATA #2 (other than the data provided) ******
/*#define MAXVOLUME 1900
int knapSack_Max_Volume = 1900;
#define MAXWEIGHT 1700
int 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 functions
void knapsack_Greedy_Algorithm();
// Structure used in the knapsack problem
typedef 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++;
}
}
// 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 selection
int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Knapsack items' array specifing their value
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Knapsack items' array specifing their volume
int 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 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}; */
// ****** End of TESTING DATA (other than the data provided) ******
// ****** Begin of TESTING DATA #2 (other than the data provided) ******
/*#define MAXVOLUME 1900
int knapSack_Max_Volume = 1900;
#define MAXWEIGHT 1700
int 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 functions
void knapsack_Greedy_Algorithm();
void knapsack_LocalSearch_Algorithm();
// Structure used in the knapsack problem
typedef 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++;
}
}
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft);
knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, volumeLeft, weightLeft);
Changed from:
while ((weightLeft > 0) && (volumeLeft > 0) && (i < linecount)) {
to:
while ((weightLeft = 0) && (volumeLeft = 0)) {
while ((weightLeft == 0) && (volumeLeft == 0)) {
cout << "knapsack_LocalSearch_Algorithm:" << endl;
cout << volumeLeft << endl;
cout << weightLeft << endl;
for (int i = 0; i < linecount; i++)
cout << SortedRatios[i] << " ";
cout << endl;
for (int i = 0; i < linecount; i++)
cout << Ratios[i] << " ";
cout << endl;
void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int volumeLeft, int weightLeft) {
const int LINE_COUNT = 10;
int itemValue[LINE_COUNT] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};
int itemVolume[LINE_COUNT] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};
int itemWeight[LINE_COUNT] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};
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.int SortedRatios[LINE_COUNT];
float Ratios[LINE_COUNT];
No need for:SortedRatios = new int[linecount];
Ratios = new float[linecount];
And the local algorithm method signature would become:void knapsack_LocalSearch_Algorithm(int SortedRatios[], float Ratios[], float tmp1, int volumeLeft, int weightLeft);
That way there's no need for you to worry about allocating/freeing dynamic memory, or using pointers directly.delete [] SortedRatios;
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.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.