Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.
// 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
// ****** Begin of ORIGINAL DATA ******
#define MAXWEIGHT 1400 // Testing Data (for Local Search)
int knapSack_Max_Weight = 1400; // Testing Data (for Local Search)
#define MAXVOLUME 1100 // Testing Data (for Local Search)
int knapSack_Max_Volume = 1100; // Testing Data (for Local Search)
int linecount = 13; // Testing Data (for Local Search)
int itemValue[13] = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50}; // Testing Data (for Local Search)
int itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200}; // Testing Data (for Local Search)
int itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200}; // Testing Data (for Local Search)
// ****** End of ORIGINAL DATA ******
// ****** Begin of 1st Data Set (10 items) ******
//#define MAXWEIGHT 1200 // Knapsack's maximum weight (constant)
//int knapSack_Max_Weight = 1200; // Knapsack's maximum weight
//
//#define MAXVOLUME 1000 // Knapsack's maximum volume (constant)
//int knapSack_Max_Volume = 1000; // Knapsack's maximum volume
//
//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 itemWeight[10] = {100, 200, 450, 200, 65, 200, 200, 350, 300, 478}; // Knapsack items' array specifing their weight
//int itemVolume[10] = {120, 200, 200, 130, 175, 200, 200, 285, 400, 422}; // Knapsack items' array specifing their volume
// ****** End of of 1st Data Set (10 items) ******
// ****** Begin of 2nd Data Set (12 items) ******
/*#define MAXWEIGHT 1350
int knapSack_Max_Weight = 1350;
#define MAXVOLUME 1150
int knapSack_Max_Volume = 1150;
int linecount = 12;
int itemValue[12] = {35, 200, 400, 300, 555, 250, 75, 122, 680, 500, 125, 275};
int itemWeight[12] = {75, 215, 333, 350, 375, 100, 75, 80, 410, 175, 100, 175};
int itemVolume[12] = {90, 222, 240, 300, 400, 177, 75, 110, 150, 350, 74, 100}; */
// ****** End of of 2nd Data Set (12 items) ******
// ****** Begin of 3rd Data Set (15 items) ******
/*#define MAXWEIGHT 1850
int knapSack_Max_Weight = 1850;
#define MAXVOLUME 2100
int knapSack_Max_Volume = 2100;
int linecount = 15;
int itemValue[15] = {200, 180, 200, 200, 200, 300, 333, 300, 515, 300, 500, 600, 900, 700, 600};
int itemWeight[15] = {150, 121, 155, 350, 50, 100, 177, 250, 420, 175, 175, 175, 575, 565, 600};
int itemVolume[15] = {120, 170, 130, 228, 55, 130, 250, 150, 288, 100, 100, 100, 700, 725, 440};*/
// ****** End of of 3rd Data Set (15 items) ******
// ****** Begin of 4th Data Set (20 items) ******
/*#define MAXWEIGHT 3000
int knapSack_Max_Weight = 3000;
#define MAXVOLUME 2875
int knapSack_Max_Volume = 2875;
int linecount = 20;
int itemValue[20] = {200, 200, 200, 200, 200, 300, 300, 300, 300, 300, 500, 600, 900, 700, 600, 250, 500, 430, 95, 250};
int itemWeight[20] = {100, 200, 150, 350, 50, 100, 200, 250, 50, 175, 175, 175, 575, 565, 600, 175, 250, 220, 25, 120};
int itemVolume[20] = {120, 200, 130, 300, 50, 120, 250, 150, 150, 100, 100, 100, 700, 725, 440, 175, 350, 320, 35, 140}; */
// ****** End of of 4th Data Set (20 items) ******
// 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:
// 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 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) << "Weight: " << setw (3) << itemWeight[SortedRatios[i]] << setw (11) << "Volume: " << setw (3) << itemVolume[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]] << " Weight: " << setw (3) << itemWeight[SortedRatios[i]] << " Volume: " << setw (3) << itemVolume[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 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;
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 << 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()){
// cout << "Item: " << (*it).Index << endl; // Output testing (console output is done via the ForLoop below)
// cout << "Value: " << (*it).Value << endl; // Output testing (console output is done via the ForLoop below)
// cout << "Volume: " << (*it).Volume << endl; // Output testing (console output is done via the ForLoop below)
// cout << "Weight: " << (*it).Weight << endl; // Output testing (console output is done via the ForLoop below)
// cout << endl << endl;
it++;
}
it = Left_Behind.begin();
while(it != Left_Behind.end()){
// cout << "Item: " << (*it).Index << endl; // Output testing (console output is done via the ForLoop below)
// cout << "Value: " << (*it).Value << endl; // Output testing (console output is done via the ForLoop below)
// cout << "Volume: " << (*it).Volume << endl; // Output testing (console output is done via the ForLoop below)
// cout << "Weight: " << (*it).Weight << endl; // Output testing (console output is done via the ForLoop below)
// cout << endl << endl;
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 << " Weight: " << setw (3) << (*it).Weight << " Volume: " << setw (3) << (*it).Volume << 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 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;
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 << 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;
}
OriginalDataSet.jpgAdd your voice to the tech community where 5M+ people just like you are talking about what matters.
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;
---> NewValue = TotalValue - SortedItems[i].Value + Left_Behind[c].Value;
if(NewWeight > knapSack_Max_Weight || NewValue<TotalValue)
break;
If you are experiencing a similar issue, please ask a related question
Join the community of 500,000 technology professionals and ask your questions.