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 <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.
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
TTimer no longer functioning | 7 | 90 | |
C++ to C# code conversion issue | 4 | 104 | |
Precision Problem in C++ | 7 | 31 | |
Embarcadero C++ builder XE10.1 Berlin TRegistry declaration | 1 | 25 |
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
11 Experts available now in Live!