I've already coded C++ years ago, but actually the language is not the problem. I'll read a bit about the knapsack to find a way to compute that.
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
int linecount = 10; // The number of objects
#define MAXWEIGHT 900
int knapSack_Max_Weight = 900;
int knapSack_Max_Volume = 800;
int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's itemValue
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's itemVolume
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's itemWeight
// Declarations of independent functions
void knapsackGreedy();
int main()
{
// Function call
knapsackGreedy();
// Pause the window console screen
system("PAUSE");
return 0;
}
void knapsackGreedy() {
int a[MAXWEIGHT]; // a[i] holds the maximum itemValue that can be obtained using at most i itemWeight
int lastAddedItem[MAXWEIGHT]; // Calculate which objects were added
int i, j;
int aux;
for (i=0; i<=knapSack_Max_Weight; ++i) {
a[i] = 0;
lastAddedItem[i] = -1;
}
a[0] = 0;
for (i=1; i<=knapSack_Max_Weight; ++i)
for (j=0; j<linecount; ++j)
if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
a[i] = a[i - itemWeight[j]] + itemValue[j];
lastAddedItem[i] = j;
}
aux = knapSack_Max_Weight;
while ((aux > 0) && (lastAddedItem[aux] != -1)) {
std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
aux -= itemWeight[lastAddedItem[aux]];
}
cout << endl << endl;
cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
}
// Required C++ libraries and header files
#include <iostream>;
#include <math.h>;
using namespace std;
#define MAXWEIGHT 900
int linecount = 10; // The number of objects
int knapSack_Max_Weight = 900;
int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's itemValue
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's itemWeight
// Declarations of independent functions
void knapsackGreedy();
void knapsack01();
typedef struct PossibleMatch {
int nItem;
int nValue;
int nWeight;
} ;
void knapsack01() {
// This method is doing a brutal check for the best match for a knapsack 0-1 by testing every possible method
int nBit;
int i;
PossibleMatch BestMatch;
PossibleMatch MyItem;
BestMatch.nValue = 0;
BestMatch.nWeight = 0;
BestMatch.nItem = 0;
for (i=1; i <= (int)pow(2.0, linecount); i++)
{
MyItem.nValue = 0;
MyItem.nWeight = 0;
for (nBit = 0; nBit <= linecount; nBit++)
{
if (i & (int)pow(2.0, nBit))
{
MyItem.nValue += itemValue[nBit];
MyItem.nWeight += itemWeight[nBit];
}
}
if ((MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nValue > BestMatch.nValue)) {
BestMatch.nItem = i;
BestMatch.nValue = MyItem.nValue;
BestMatch.nWeight = MyItem.nWeight;
}
}
// Display the best result
for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
{
if (BestMatch.nItem & (int)pow(2.0,nBit)) {
std::cout << "Added item #" << (nBit+1) << std::endl;
}
}
}
void knapsackGreedy() {
int a[MAXWEIGHT]; // a[i] holds the maximum itemValue that can be obtained using at most i itemWeight
int lastAddedItem[MAXWEIGHT]; // Calculate which objects were added
int i, j;
int aux;
for (i=0; i<=knapSack_Max_Weight; ++i) {
a[i] = 0;
lastAddedItem[i] = -1;
}
a[0] = 0;
for (i=1; i<=knapSack_Max_Weight; ++i)
for (j=0; j<linecount; ++j)
if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
a[i] = a[i - itemWeight[j]] + itemValue[j];
lastAddedItem[i] = j;
}
aux = knapSack_Max_Weight;
while ((aux > 0) && (lastAddedItem[aux] != -1)) {
std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
aux -= itemWeight[lastAddedItem[aux]];
}
cout << endl << endl;
cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
};
int main()
{
// Function call
knapsack01();
// Pause the window console screen
system("PAUSE");
return 0;
}
void knapsackGreedy01() {
int SortedRatios[10];
float Ratios[10];
float tmp1;
int weightLeft = MAXWEIGHT;
int i, j;
// Calculate the ratios
for (i=0; i < 10; i++) {
Ratios[i] = (float)itemValue[i] / itemWeight[i];
SortedRatios[i] = i;
}
// Sort them
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;
}
}
// Get the best values, by choosing unique items
i = 0;
while (weightLeft > 0) {
if (weightLeft - itemWeight[SortedRatios[i]] >= 0) {
weightLeft -= itemWeight[SortedRatios[i]];
std::cout << "Added item #" << SortedRatios[i++] + 1 << std::endl;
}
else {
break;
}
}
}
// Required C++ libraries and header files
#include <iostream>
#include <math.h>
using namespace std;
// DATA SET #1:
//#define MAXWEIGHT 5
//#define MAXVOLUME 6 // NOT YET IMPLEMENTED!!!
//
//int linecount = 3; // The number of objects
//int knapSack_Max_Weight = 5; // Max weight
//int knapSack_Max_Volume = 6; // Max volume -- NOT YET IMPLEMENTED!!!
//int itemValue[3] = {5, 3, 4}; // Item's itemValue
//int itemWeight[3] = {2, 4, 3}; // Item's itemWeight
//int itemVolume[3] = {2, 3, 2}; // Item's itemVolume -- NOT YET IMPLEMENTED!!!
// DATA SET #2:
#define MAXWEIGHT 800
#define MAXVOLUME 900 // NOT YET IMPLEMENTED!!!
int linecount = 10; // The number of objects
int knapSack_Max_Weight = 800; // Max weight
int knapSack_Max_Volume = 900; // Max volume
int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's itemValue
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's itemWeight
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's itemVolume -- NOT YET IMPLEMENTED!!!
// Declarations of independent functions
void knapsackGreedy();
void knapsack01();
typedef struct PossibleMatch {
int nItem;
int nValue;
int nWeight;
int nVolume;
};
void knapsack01() {
// This method is doing a brutal check for the best match for a knapsack 0-1 by testing every possible method
int nBit;
int i;
PossibleMatch BestMatch;
PossibleMatch MyItem;
BestMatch.nValue = 0;
BestMatch.nWeight = 0;
BestMatch.nVolume = 0;
BestMatch.nItem = 0;
for (i=1; i <= (int)pow(2.0, linecount); i++)
{
MyItem.nValue = 0;
MyItem.nWeight = 0;
MyItem.nVolume = 0;
for (nBit = 0; nBit <= linecount; nBit++)
{
if (i & (int)pow(2.0, nBit))
{
MyItem.nValue += itemValue[nBit];
MyItem.nWeight += itemWeight[nBit];
MyItem.nVolume += itemVolume[nBit];
}
}
if ((MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nVolume <= knapSack_Max_Volume) && (MyItem.nValue > BestMatch.nValue)) {
BestMatch.nItem = i;
BestMatch.nValue = MyItem.nValue;
BestMatch.nWeight = MyItem.nWeight;
BestMatch.nVolume = MyItem.nVolume;
}
}
// Display the best result
for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
{
if (BestMatch.nItem & (int)pow(2.0,nBit)) {
std::cout << "Added item #" << (nBit+1) << std::endl;
}
}
}
void knapsackGreedy01() {
int SortedRatios[10];
float Ratios[10];
float tmp1;
int weightLeft = MAXWEIGHT;
int volumeLeft = MAXVOLUME;
int i, j;
// Calculate the ratios
for (i=0; i < 10; i++) {
Ratios[i] = (float)itemValue[i] / itemWeight[i];
SortedRatios[i] = i;
}
// Sort them
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;
}
}
// Get the best values, by choosing unique items
i = 0;
while (weightLeft > 0) {
if (weightLeft - itemWeight[SortedRatios[i]] >= 0) {
weightLeft -= itemWeight[SortedRatios[i]];
std::cout << "Added item #" << SortedRatios[i++] + 1 << std::endl;
}
else {
break;
}
}
}
int main()
{
// Function call
knapsack01();
// Pause the window console screen
system("PAUSE");
return 0;
}
// Required C++ libraries and header files
#include <iostream>;
#include <math.h>;
using namespace std;
#define MAXWEIGHT 900
#define MAXVOLUME 800
int linecount = 10; // The number of objects
int knapSack_Max_Weight = 900;
int knapSack_Max_Volume = 800;
int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's Value
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's Weight
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's Volume
// Declarations of independent functions
void knapsackGreedy();
void knapsackGreedy01();
void knapsack01();
typedef struct PossibleMatch {
int nItem;
int nValue;
int nWeight;
int nVolume;
} ;
void knapsack01() {
// This method is doing a brutal check for the best match for a knapsack 0-1 by testing every possible method
int nBit;
int i;
PossibleMatch BestMatch;
PossibleMatch MyItem;
BestMatch.nValue = 0;
BestMatch.nWeight = 0;
BestMatch.nVolume = 0;
BestMatch.nItem = 0;
for (i=1; i <= (int)pow(2.0, linecount); i++)
{
MyItem.nValue = 0;
MyItem.nWeight = 0;
MyItem.nVolume = 0;
for (nBit = 0; nBit <= linecount; nBit++)
{
if (i & (int)pow(2.0, nBit))
{
MyItem.nValue += itemValue[nBit];
MyItem.nWeight += itemWeight[nBit];
MyItem.nVolume += itemVolume[nBit];
}
}
if ((MyItem.nVolume <= knapSack_Max_Volume) && (MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nValue > BestMatch.nValue)) {
BestMatch.nItem = i;
BestMatch.nValue = MyItem.nValue;
BestMatch.nWeight = MyItem.nWeight;
BestMatch.nVolume = MyItem.nVolume;
}
}
// Display the best result
for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
{
if (BestMatch.nItem & (int)pow(2.0,nBit)) {
std::cout << "Added item #" << (nBit+1) << std::endl;
}
}
}
void knapsackGreedy01() {
int SortedRatios[10];
float Ratios[10];
float tmp1;
int weightLeft = MAXWEIGHT;
int volLeft = MAXVOLUME;
int i, j;
// Calculate the ratios
for (i=0; i < 10; i++) {
Ratios[i] = (float)itemValue[i] / itemWeight[i];
SortedRatios[i] = i;
}
// Sort them
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;
}
}
// Get the best values, by choosing unique items
i = 0;
while (weightLeft > 0) {
if ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volLeft - itemVolume[SortedRatios[i]] >= 0)) {
weightLeft -= itemWeight[SortedRatios[i]];
volLeft -= itemVolume[SortedRatios[i]];
std::cout << "Added item #" << SortedRatios[i++] + 1 << std::endl;
}
else {
break;
}
}
}
void knapsackGreedy() {
int a[MAXWEIGHT]; // a[i] holds the maximum itemValue that can be obtained using at most i itemWeight
int lastAddedItem[MAXWEIGHT]; // Calculate which objects were added
int i, j;
int aux;
for (i=0; i<=knapSack_Max_Weight; ++i) {
a[i] = 0;
lastAddedItem[i] = -1;
}
a[0] = 0;
for (i=1; i<=knapSack_Max_Weight; ++i)
for (j=0; j<linecount; ++j)
if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
a[i] = a[i - itemWeight[j]] + itemValue[j];
lastAddedItem[i] = j;
}
aux = knapSack_Max_Weight;
while ((aux > 0) && (lastAddedItem[aux] != -1)) {
std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
aux -= itemWeight[lastAddedItem[aux]];
}
cout << endl << endl;
cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
};
int main()
{
// Function call
knapsack01();
// Pause the window console screen
system("PAUSE");
return 0;
}
// Required C++ libraries and header files
#include <iostream>;
#include <math.h>;
using namespace std;
#define MAXWEIGHT 900
#define MAXVOLUME 800
int linecount = 10; // The number of objects
int knapSack_Max_Weight = 900;
int knapSack_Max_Volume = 800;
int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's Value
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's Volume
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's Weight
// Declarations of independent functions
void knapsackGreedy();
void knapsackGreedy01();
void knapsack01();
// Structure used with knapsack01
typedef struct PossibleMatch {
int nItem;
int nValue;
int nWeight;
int nVolume;
} ;
void knapsack01() {
// This function will check for EVERY possible combination, and will keep the best value at the end.
// There's no logic for ratio "value/weight", therefore it's slower and is more suitable when the number
// of items are limited. When having a lot of items, it would be better to use knapsackGreedy01.
//
// It use an integer as a binary array since you can add an item only once to the sack.
int nBit;
int i;
PossibleMatch BestMatch;
PossibleMatch MyItem;
BestMatch.nValue = 0;
BestMatch.nWeight = 0;
BestMatch.nVolume = 0;
BestMatch.nItem = 0;
// Loop from 1 to the highest value generated by "x bits". If you got 10 items, then you got to use 10 bits. So you have 2^10 possibilities (1024 possibilities).
for (i=1; i <= (int)pow(2.0, linecount); i++)
{
// Reset the current item
MyItem.nValue = 0;
MyItem.nWeight = 0;
MyItem.nVolume = 0;
// Calculate the value, weight and volume based on the actual possibility
for (nBit = 0; nBit <= linecount; nBit++)
{
// Check if the bit is at 1 in this possibility:
if (i & (int)pow(2.0, nBit))
{
// The bit is ON so it mean that the item need to be inserted
MyItem.nValue += itemValue[nBit];
MyItem.nWeight += itemWeight[nBit];
MyItem.nVolume += itemVolume[nBit];
}
}
// After adding all these items to the sack, we need to check if we exceed the Weight & Volume.
// If we don't exceed it, we must check if it's value is higher than the best we have seen so far...
if ((MyItem.nVolume <= knapSack_Max_Volume) && (MyItem.nWeight <= knapSack_Max_Weight) && (MyItem.nValue > BestMatch.nValue)) {
// This possibility (combination) is better. So we memorize it, and it's total Value/Weight/Volume to display the best result
BestMatch.nItem = i;
BestMatch.nValue = MyItem.nValue;
BestMatch.nWeight = MyItem.nWeight;
BestMatch.nVolume = MyItem.nVolume;
}
}
// Display the best result, by checking which bits are ON in that combination.
for (nBit=0; nBit <= (int)pow(2.0, linecount); nBit++)
{
if (BestMatch.nItem & (int)pow(2.0,nBit)) {
std::cout << "Added item #" << (nBit+1) << " Weight: " << itemWeight[nBit] << ", Volume: " << itemVolume[nBit] << ", Value: " << itemValue[nBit] << std::endl;
}
}
std::cout << "Total Weight: " << BestMatch.nWeight << std::endl;
std::cout << "Total Volume: " << BestMatch.nVolume << std::endl;
std::cout << "Total Value: " << BestMatch.nValue << std::endl;
}
void knapsackGreedy01() {
// This function will create a knapsack using a greedy method: That mean that it build a
// table of ratios "Value/Weight", then it sort it in descending order to have the highest
// ratio on top. Once it's done, it add 1 item of each until there's no more space for
// the next item.
//
// It might leave the knapsack with some free space and nothing else to fill up because every other
// items weight are too high. Therefore, this method is not optimal and could benefit from Local Search
// function.
//
// Since this method is really fast, it can be used with a huge number of items.
int SortedRatios[10]; // Index of ratios
float Ratios[10]; // Ratios themselves
float tmp1;
int weightLeft = MAXWEIGHT;
int volLeft = MAXVOLUME;
int totalValue = 0;
int i, j;
// Calculate the ratios for each items
for (i=0; i < 10; i++) {
Ratios[i] = (float)itemValue[i] / itemWeight[i];
SortedRatios[i] = i;
}
// Sort them using a Bubble Sort (check for wiki for more details)
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;
}
}
// Adding items with the best value/weight ratio first, and add others until we reach the weight limit.
// Display each item as soon as we add them to the sack.
i = 0;
while (weightLeft > 0) {
// We make sure that the next combination won't make us go over the Volume & Weight limits that we have fixed
if ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volLeft - itemVolume[SortedRatios[i]] >= 0)) {
// We are not going to reach the limit, so we add the item in the sack
weightLeft -= itemWeight[SortedRatios[i]];
volLeft -= itemVolume[SortedRatios[i]];
std::cout << "Added item #" << SortedRatios[i] + 1 << " Weight: " << itemWeight[ SortedRatios[i]] << ", Volume: " << itemVolume[ SortedRatios[i]] << ", Value: " << itemValue[ SortedRatios[i]] << std::endl;
totalValue += itemValue[ SortedRatios[i]];
i++;
}
else {
break;
}
}
std::cout << "Total Weight: " << knapSack_Max_Weight - weightLeft << std::endl;
std::cout << "Total Volume: " << knapSack_Max_Volume - volLeft << std::endl;
std::cout << "Total Value: " << totalValue << std::endl;
}
void knapsackGreedy() {
int a[MAXWEIGHT]; // a[i] holds the maximum itemValue that can be obtained using at most i itemWeight
int lastAddedItem[MAXWEIGHT]; // Calculate which objects were added
int i, j;
int aux;
for (i=0; i<=knapSack_Max_Weight; ++i) {
a[i] = 0;
lastAddedItem[i] = -1;
}
a[0] = 0;
for (i=1; i<=knapSack_Max_Weight; ++i)
for (j=0; j<linecount; ++j)
if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
a[i] = a[i - itemWeight[j]] + itemValue[j];
lastAddedItem[i] = j;
}
aux = knapSack_Max_Weight;
while ((aux > 0) && (lastAddedItem[aux] != -1)) {
std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
aux -= itemWeight[lastAddedItem[aux]];
}
cout << endl << endl;
cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
};
int main()
{
// Function call
knapsackGreedy01();
// Pause the window console screen
system("PAUSE");
return 0;
}
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
//#define MAXVOLUME 800
//int knapSack_Max_Volume = 800;
//
//#define MAXWEIGHT 900
//int knapSack_Max_Weight = 900;
//
//int linecount = 10; // The number of objects
//int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's Value
//int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's Volume
//int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's Weight
#define MAXVOLUME 1100
int knapSack_Max_Volume = 1100;
#define MAXWEIGHT 1400
int knapSack_Max_Weight = 1400;
int linecount = 13; // The number of objects
int itemValue[13] = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50}; // Item's Value
int itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200}; // Item's Volume
int itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200}; // Item's Weight
// Declarations of independent functions
void knapsack_Greedy_LocalSearch();
// Structure used with knapsack
typedef struct PossibleMatch {
int nItem;
int nValue;
int nVolume;
int nWeight;
} ;
// Main() is the programs' "entry point"
int main()
{
// Function call
knapsack_Greedy_LocalSearch();
// Pause the window console screen
system("PAUSE");
return 0;
}
void knapsack_Greedy_LocalSearch() {
// This function will check for EVERY possible combination, and will keep the best value at the end.
// There is no logic for ratio "value/weight", therefore it's slower and is more suitable when the number
// of items are limited.
// This solution uses an integer as a binary array since it can add an item only once to the sack.
//
// It might leave the knapsack with some free space and nothing else to fill up because every other
// items weight are too high. Therefore, this method is not optimal and could benefit from Local Search
// function.
//
// Since this method is really fast, it can be used with a huge number of items.
int SortedRatios[10]; // Index of ratios
float Ratios[10]; // Ratios themselves
float tmp1;
int volumeLeft = MAXVOLUME;
int weightLeft = MAXWEIGHT;
int totalValue = 0;
int i, j;
// Calculate the ratios for each items
for (i=0; i < 10; i++) {
Ratios[i] = (float)itemValue[i] / itemWeight[i];
SortedRatios[i] = i;
}
// Sort them using a Bubble Sort (check for wiki for more details)
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;
}
}
// Adding items with the best value/weight ratio first, and add others until we reach the weight limit.
// Display each item as soon as we add them to the sack.
i = 0;
while (weightLeft > 0) {
// We make sure that the next combination won't make us go over the Volume & Weight limits that we have fixed
if ((volumeLeft - itemVolume[SortedRatios[i]] >= 0) && (weightLeft - itemWeight[SortedRatios[i]] >= 0)) {
// We are not going to reach the limit, so we add the item in the sack
volumeLeft -= itemVolume[SortedRatios[i]];
weightLeft -= itemWeight[SortedRatios[i]];
std::cout << "Added item #: " << setw (5) << SortedRatios[i] + 1 << " Value: " << itemValue[SortedRatios[i]] << " Volume: " << itemVolume[SortedRatios[i]] << " Weight: " << itemWeight[SortedRatios[i]] << std::endl;
totalValue += itemValue[SortedRatios[i]];
i++;
}
else {
break;
}
}
std::cout << endl;
std::cout << "Total Volume: " << setw (5) << knapSack_Max_Volume - volumeLeft << std::endl;
std::cout << "Total Weight: " << setw (5) << knapSack_Max_Weight - weightLeft << std::endl;
std::cout << "Total Value: " << setw (5) << totalValue << std::endl;
std::cout << endl << endl;
}
DifferentDataSet.jpgFinal question... how come the sorting order changed from (1, 3, 6, 10) to (3, 6, 1, 10). 'Just curious
Ratios[i] = (float)itemValue[i] / itemWeight[i];
Ratios[i] = (float)itemValue[i] / (itemVolume[i] + itemWeight[i]);
void knapsackGreedy01() {
// This function will create a knapsack using a greedy method: That mean that it build a
// table of ratios "Value/Weight", then it sort it in descending order to have the highest
// ratio on top. Once it's done, it add 1 item of each until there's no more space for
// the next item.
//
// It might leave the knapsack with some free space and nothing else to fill up because every other
// items weight are too high. Therefore, this method is not optimal and could benefit from Local Search
// function.
//
// Since this method is really fast, it can be used with a huge number of items.
int *SortedRatios; // Index of ratios
float *Ratios; // Ratios themselves
float tmp1;
int weightLeft = MAXWEIGHT;
int volLeft = 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 them using a Bubble Sort (check for wiki for more details)
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;
}
}
// This code is used to show the Bubble Sort result to see if it's sorted per ratio properly
//std::cout << "Tableau des ratios" << std::endl;
//for (i=0; i<linecount; i++) {
// std::cout << "Ratios: " << Ratios[i] << ", Index: " << SortedRatios[i] << ", Weight: " << itemWeight[SortedRatios[i]] << ", Value: " << itemValue[SortedRatios[i]] << ", Volume: " << itemVolume[SortedRatios[i]] << std::endl;
//}
//std::cout << std::endl << std::endl;
// Adding items with the best value/weight ratio first, and add others until we reach the weight limit.
// Display each item as soon as we add them to the sack.
i = 0;
while ((weightLeft > 0) && (volLeft > 0) && (i < linecount)) {
// We make sure that the next combination won't make us go over the Volume & Weight limits that we have fixed
if ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volLeft - itemVolume[SortedRatios[i]] >= 0)) {
// We are not going to reach the limit, so we add the item in the sack
weightLeft -= itemWeight[SortedRatios[i]];
volLeft -= itemVolume[SortedRatios[i]];
std::cout << "Added item #" << SortedRatios[i] + 1 << " Weight: " << itemWeight[ SortedRatios[i]] << ", Volume: " << itemVolume[ SortedRatios[i]] << ", Value: " << itemValue[ SortedRatios[i]] << std::endl;
totalValue += itemValue[ SortedRatios[i]];
}
i++;
}
std::cout << "Total Weight: " << knapSack_Max_Weight - weightLeft << std::endl;
std::cout << "Total Volume: " << knapSack_Max_Volume - volLeft << std::endl;
std::cout << "Total Value: " << totalValue << std::endl;
}
std::cout << "Ratios: " << setw (8) << Ratios[i] << setw (10) << "Index: " << setw (2) << SortedRatios[i] ....
std::cout << "Ratios: " << fixed << setprecision(2) << Ratios[i] << std::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++;
}
}
Repeated violations are considered an abuse of EE's systems, and the behavior will result in consequences.
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
20 Experts available now in Live!