Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.
// 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;
}
// 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.
// ************************************************************************************************
If you are experiencing a similar issue, please ask a related question
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
11 Experts available now in Live!