// 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 (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) ******
// 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 weightLeft = MAXWEIGHT;
int volumeLeft = MAXVOLUME;
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 ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volumeLeft - itemVolume[SortedRatios[i]] >= 0)) {
// Passing the If-statement ensure that space is left in the knapsack. Therefore, the item is added to the knapsack.
weightLeft -= itemWeight[SortedRatios[i]];
volumeLeft -= itemVolume[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;
}
Data-Set-1-vs.-Data-Set-2----plu.xls
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
Detect CR LF to each line | 12 | 161 | |
Global Keyboard Hooks Blocked | 4 | 77 | |
How to learn Linux? | 10 | 61 | |
Embarcadero C++ Builder XE10.1 Berlin red arrow Indicator | 2 | 36 |
Join the community of 500,000 technology professionals and ask your questions.