Right now, I've developed the basic framework (I googled for existing code and tried to modify it).

At this point, the code below somewhat works. By "somewhat", I mean that it doesn't meet the "0-1 Knapsack" concept. Essentially, the program adds four items of #3 (based on its greatest value contribution)... and then adds #1 due to the remaining (unfilled) weight capacity.

So, while the code does determine the greatest value contribution, I want to modify it so that I only can add one item at the most to the knapsack.

Does anyone know how to add this constraint (i.e, once an added has been selected for the knapsack, remove it from the array so that I can't be selected again)?

Thx,
EEH

P.S. Also, as this is not my original code, I'm having a tough time understanding the ForLoop and WhileLoop. If anyone could "walk me through" this (by adding a few comments), it would greatly help me in the continuation of the program development. Again, thanks!!!

P.S.S. If you think that this code is too cumbersome and could work better using a different method, I"m open to recommendations.

// 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 900int knapSack_Max_Weight = 900;int knapSack_Max_Volume = 800;int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's itemValueint itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's itemVolumeint itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's itemWeight// Declarations of independent functionsvoid 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;}

According to Wikipedia article, Greedy approximation algorithm is not the best method for 0-1. You could probably add some conditions to add 1 item of each maximum, but it wouldn't be optimal.

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.

And, yes, you're right, "Greedy" won't give the optimal solution. This however is only step 1 out of two steps. I can/will have to improve the Greedy algorithm with a "Local Search" method. That's a different problem though.

For right now, I'll be happy if I can get the "Greedy" algorithm to work... or modify the existing code by adding the constraint.

I've tried to think about the best way to solve this problem, and i don't see any better solution than checking every possibles combinations. There's probably some algorythm for that, but i've not found any.

This method is good because it help you to find the best value for your knapsack, but more you will have objects to pick-up, more it will take time. Actually for 10 items, it's really fast. But if you would get 30 items, i would think about using a Greedy method instead of this one.

// Required C++ libraries and header files#include <iostream>;#include <math.h>;using namespace std;#define MAXWEIGHT 900int 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 itemValueint itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's itemWeight// Declarations of independent functionsvoid 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;}

Wow... you're truly a "guru". I really really appreciate your expertise on this subject. Ok, I've tested both solution with three data sets. All of them give me the expected output.... YEAH!!!! 8)

When compiling, I noticed several warnings. These are:
warning C4067: unexpected tokens following preprocessor directive - expected a newline
warning C4067: unexpected tokens following preprocessor directive - expected a newline
warning C4091: 'typedef ' : ignored on left of 'PossibleMatch' when no variable is declared
warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
warning C4244: '=' : conversion from 'float' to 'int', possible loss of data

Should I simply ignore them?

Btw, I just realized that I forgot to mention one element in the original posting. I TRULY HOPE THIS WON'T CAUSE YOU MAJOR FRUSTRATION WITH ME.

Essentially, the code that I had found included the items "values" and "weights", where the sum of the items' weights could not exceed the knapsack's capacity. There's a second constraint that I would like to include. This could covers "volume".

The approach is identical to weight the weight concept. I cannot exceed the max volume.

So, again, instead just keeping weight in mind, I would like to keep "weight AND volume" in mind.
The values for all three are:

... where Max Volume = 800 volume units and Max Weight = 900 weight units

Can the second constraint (volume) be tied in this code? If yes how?

For right now, this is the next step that I'd like to achieve. However, allow me to also mentioned another piece of information. See below "break".

BREAK

Now, to your questions. I completely appreciate your point on optimization (i.e., processing speed). Based on your assessment, which one would you recommend (solution #1 or #2).

Well, maybe the following will help getting before you answer this question. As mentioned in posting http:#34938919, the "Greedy" method is step 1 out of 2.

Again, it seems that either approach addresses step 1. Now to step 2.... I'd like include a "Local Search" algorithm. What does that mean? Well, I could provide a major rewrite on this, but the basics are covered at: http://en.wikipedia.org/wiki/Local_search_%28constraint_satisfaction%29

Essentially, my "Greedy" gives me (potentially) in near to optimal solution. Forget for a moment that I know what the optimal solution is (based on having used your Excel solution a few days ago).

The Local Search will take the Greedy's method and gradually "attempt" to improve it. This could be done by swapping items' in and out.

But again, unless the "Local Search" should be considered in this development stage right now, adding the "volume constraint" is more important to me at this moment.

Btw, I truly appreciate your help (again). Your expertise and patience make this forum truly the best place on the web.

In respect to the 2nd constraint (volume), I've taken a stab at it. It seemed straight-forward until I hit the function << knapsackGreedy01 <<. More specifically, I wasn't sure how to include it into the "ratio" calculation.

Thoughts/recommendations for this step (thus far)?

EEH

// 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 weightint knapSack_Max_Volume = 900; // Max volumeint itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Item's itemValueint itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's itemWeightint itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's itemVolume -- NOT YET IMPLEMENTED!!!// Declarations of independent functionsvoid 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;}

About your concerns with warnings, you could ignore them. If they bug you, they are easy to solve by clicking on them. I'm using VS2010 and it doesn't produce any warning at the moment with this code.

ex: "possible loss of data" is caused by a float temporary variable (tmp1) assigned to an int variable. It doesn't cause any loss because i know that what is inside tmp1 at this moment is really an Integer.

---

As i've mentionned, if you use small amounts of items, solution knapsack01 is the best since it give you the best value for your knapsack. If you have a lot of items, i would choose solution knapsackGreedy01 because it's way faster. (but it might have a slightly better match)

----

Don't worry for the question for volume, i'm not bugged by that. But keep in mind that other people might help you better if you ask a new question.

So here is how i would do it to implement the volume. I've implemented it in both solutions, but i don't really know if it's efficient in knapsackGreedy01 since i don't do any ratio based on volume. And i guess that the best ratio would be a combination of volume+weight, not only weight. But knapsack01 as usual give the optimal value per volume/weight.

// Required C++ libraries and header files#include <iostream>;#include <math.h>;using namespace std;#define MAXWEIGHT 900#define MAXVOLUME 800int 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 Valueint itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's Weightint itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's Volume// Declarations of independent functionsvoid 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;}

I see that we got the same idea for the knapsack01, and the same problem in the greedy01 version.

I've no clue how to check for that in that algorithm. For the moment, my version only make sure that you don't go over the limit of volume, but the final solution might not be optimal. Greedy algorithm is an approximation anyway. There might be a way to combine 2 ratios together but which one would have more importance?

Again, thousand thanks for your help!!! It is much appreciated.

Quick follow-up question about the program. Currently, it's calling

void knapsackGreedy();
void knapsackGreedy01();

Given that I'm only dealing w/ a small data set right now, are they duplicative? Shall I remove one... or do the Greedy and Greedy01 depend on each other?

Also, final question... is there's a chance for you to include to very basic/quick comments (not every line) but for the major functions/computations.

That'll allow me to study your logic and make better sense of it.

knapsackGreedy01 = knapsack01. Both are solving the 0-1 problem of the knapsack.

knapsackGreedy is used to solve the Unbounded knapsack problem. (so this version will give a result with many time the same item and few others to fill up the pack).

So both are addressing different problem, therefore both should be kept. To choose between knapsackGreedy01 and knapsack01, you could check how many items you got, and if you have more than 20 items for example, then you would use knapsackGreedy01.

I'll add some comments and come back in few minutes

Wow... I just realized that your algorithm (based on this data set) actually hits the optimal solution.

As you stated >> ".... the final solution might not be optimal" <<, the Greedy method provides only an approximate solution. It is the Local Search that might improve it via small iterations.

However, I just compared the output of your Greedy01 solution with the one in Excel. Both produce (1, 3, 6, 10) as the optimal solution.

So, somewhere in your code, you actually solved the "Local Search".... TOTALLY COOL!!!

Hopefully I can see from your comments which lines of code might fall into the "greedy" or "local search" category.

Again, I'm thrilled about the help you provided me.

Yes, the Local Search problem is solved by knapsack01. But if you choose another method, like an unbounded method, you will have to figure out how to do it, or just use a knapsack01 similar method (it would require to use an array of Int instead of a simple Int (because you got to store values, not only 0 or 1).

I've commented everything, except the function that you already provided because i don't really understand this method. I've added code to display the weight/volume/value of each items added to the sack, and give a summary once it's completed

// Required C++ libraries and header files#include <iostream>;#include <math.h>;using namespace std;#define MAXWEIGHT 900#define MAXVOLUME 800int 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 Valueint itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Item's Volumeint itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Item's Weight// Declarations of independent functionsvoid knapsackGreedy();void knapsackGreedy01();void knapsack01();// Structure used with knapsack01typedef 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;}

Oh my... hopefully I didn't cheer too prematurely.

I know you're busy... but I just wanted to share w/ you that I didn't get the optimal solution with another data set (using 13 arbitrary records).

See attached snapshots (console and XLS view).

Sounds like the "Local Search" is required to gradually improve the outcome. I'm just confused as to why the 10 original records game the the optimal solution (verified by Excel)... but an additional 3 records makes it not even come close.

Thoughts/recommendations?

// 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 1100int knapSack_Max_Volume = 1100;#define MAXWEIGHT 1400int knapSack_Max_Weight = 1400; int linecount = 13; // The number of objectsint itemValue[13] = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50}; // Item's Valueint itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200}; // Item's Volumeint itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200}; // Item's Weight// Declarations of independent functionsvoid knapsack_Greedy_LocalSearch();// Structure used with knapsacktypedef 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;}

ok... there's some stuffs that slips out of my hands. Sorry for that.

Search for every "10" in your file... you will notice that in a loop, i should have specified "linecount" (just like the other FOR loops).

At line 85 in your code, it should be: for (i=0; i < linecount; i++)

Line 76 and 77 are also wrong because i hardcoded 10. But you can't use linecount (a variable) to define the array size. So you could define them as pointer, and dynamically resize the array based on line count like this:

int *SortedRatios; // Index of ratios
float *Ratios; // Ratios themselves
SortedRatios = new int[linecount];
Ratios = new float[linecount];

But it's not the only problem, i need a little more time to find what's going on

Yes, that actually fixed some access violation errors. Up until this change, the program 'blew up" (after it produced the output).

Even after this change though, the data set having 13 records does NOT produce the optimal output as the data set having 10 records did.

I'm wondering if the first data set provided the optimal solution by mere coincidence or if indeed it used "brute force" to determine it. If the latter is the case, I don't know why it didn't work for the second data set.

I think I understand as to why the solution for data set #1 and data set #2 result in an optimal and not optimal solution, respectively.

In data set #1, the values for weight and volume and nearly identical except for items 9 and 10. That is NOT the case at all for data set #2.

Once I reviewed the code again, I noticed that the ratio was computed only based on weight.
I changed it to include "volume" as well. See code below.

Once that was done, the output for data set #1 remained unchanged (given that the ratio didn't change except a tiny bit due to items 9 and 10).

However, the output for data set #2 changed and came much "closer" to the optimal solution. Essentially, the total value changed from 960 to 1655. Obviously, it is still off by 300+ from optimal solution (see Excel's answer of 1980), but I at least know that my solution only contains the "Greedy" method.

It was not the only problem. There was a problem with the index.
At the end i was incrementing the "i" variable only if i could place an item in the sack. But it was not right to do that because it's sorted by ratio, not by weight. So other items could have been placed in the sack. So i've modified this piece of code. I've also added your ratio based on volume and weight. The result i get is a value of 1805, weight of 680, and Volume of 950.

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;}

Post another question. I'll add you in the list of people that i'll follow. If no one answer, might give it a try but for the moment i got to do some work.

Thanks... that's awesome... the optimal value (1805) of the second data set (I presume) is very close to the "real" optimal value.

I don't have C++ here at work... but I will check it out asap tonight. Again, thanks for continuing to monitor this thread and offering your help. I am very grateful for that.

I'll do further reading on the "Local Search". I'm trying to meet my work deadline for early next week... but hey, that's a whole week from now.

If (more than likely) I get stuck, I'll post another question. And, thanks, for adding me to the list of people you follow. 'Much appreciated.

Cool... I wish I had the "smarts" for being a programmer. However, I'm learning right now... I guess that's the most important thing, right. Open expand your mind to new options.

Ok... I've opened another question with -- I think -- a good background on what I'm trying to achieve. If you're interested, I welcome you to have a look at:

Given your familiarity of this program, could you please provide me a basic hint as to how I can achieve the following:

1. Select an item (randomly) that has been added to the knapsack.
2. Select an item that is NOT in the knapsack.
3. Swap them (meaning replacing the two selected items). Compute the new total value. If the value is greater, keep the new item. Otherwise, take it out and return the original item.
4. Repeat steps 1 to 3. Stop after n iterations.

I'm just not sure how to get started. W/ a few hints, I might be able getting somewhere. 8)

EEH

P.S. I've done my "homework" on "Local Search"... just not finding good tips online for actually implementing the algorithm.

I know it's for your course, i've watched some of your thread where some people refuse to help because E-E is not there to do your homework.

The 4 steps that you have mentionned are ok. All you need now is to translate this into C++... this is the easiest part. If you get any question on C++ programming, for example, if you don't know how to generate random numbers, then feel free to ask.

You already know that you got to create a loop to stop after N iteration. So you got to do a Do While or something like that.

In that loop, you know that you need to have 2 random numbers to access your array. One should give you the index of an item that is in your sack, the other point to an item that is not in the sack. So you know that you have to put these items into 2 different array, or sort them. To get a random number, you can use srand and rand functions. Google if you don't know how to use them, it's quite easy to find.

You already know how to compute what it's in your sack. You already got the array with volume & weight.

You know how to make a loop, how to access an array, etc... so go ahead.

If this is not for your homework, then maybe the company you are working for need to pay someone to give you some help with the coding if you are not a programmer yourself.

Oh and by the way, what sdeller said about the Bubble Sort in the other post, of course this is not the best method on earth. But since you have shown only few data (10 and 13 data only), Bubble Sort is the easiest method to remember.

There's more advanced techniques to sort things, but why the hell would i have wrote code for a balanced tree when 2 stupid loops do the job? neh!

Thanks for the hints.... every time I hear the term "arrays" I choke (smile).

I'll check it out the next couple of days/nights... definitely this weekend. I'm sure I get something going.

If I do have questions, I feel bad posting them here since this question is officially closed. I just want to make sure you get the recognition for the help that you provide me.

If you feel bad, just post another question. But like many other says, your question should should be about a specific subject, and you should already have some code or tried something before posting. Never ask a question where you ask to experts to give you the answer from A to Z.

If you have difficulties with these concepts, then maybe you are not fit for computer programming. You got to understand those concepts.

If you are doing this for your courses at school, then you just post-pone the problem... you won't fail now at your courses, but you will fail later at your job.

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++; }}

Hello again... I hope you're still getting notified when updates are made to a message.

You provided me some awesome help (about a month ago).

I've run the problem with different data sets now and I'm getting a strange output (a negative delta returns some 10-digit number vs. the actual difference).

Netminder, may i ask you what you have read in this solution? You spotted the word "EMAIL" and decided to slam us because we dare pronounced that word? I do agree with ExpExchHelp on that, you are really making up stuff!

If you check at my last comment, i said something like: "You already got the answer, if you need me to check at other thread, just send me an email"

Why the hell E-E would accept that their users come up here and say: "Hey, I've posted another question somewhere else and nobody seems to help. You seems to have some knowledge of my code and about the subject i'm working on, could you take a look at it?".

If E-E accept that, then it mean that it accept that all their solutions to become a total junkyard! Like our actual comments... which is absolutely not necessary to this question. So if someone come up on E-E and check at this solution, the first words that will come up to their mind is: "What the heck!?!?"

Oh and NetMinder, i'm also a paying member. The only reason why i helped is because I WANTED TO HELP. That's all... We didn't exchanged any email, and as you can see, ExpExchHelp posted a new thread and asked me to take a look at it here, that should ring you a bell that he didn't mailed me! Understood Sherlock?

Netminder: And if you think that my last comment has a total lack of profesionnalism, the way that you have threated me is TOTALLY NOT PROFESSIONNAL.

I will not accept that kind of behavior. If you insult people, expect them to punch back!

The next time that you snap me with that kind of shit, don't think i'll leave that behind and accept that.

Repeated violations are considered an abuse of EE's systems, and the behavior will result in consequences.

At least, you should explain yourself. I can't understand that you arrived to the conclusion that we emailed each other when ExpExchHelp keep asking me to check at other thread PUBLICLY, HERE IN THIS THREAD. (See those comments for yourself: 35210917, 34987979, 34985361)

For your info, i've just created a PDF file in case you decide to delete this thread. Because if i get that kind of shit again, i'll gladly give a call to Experts-Exchange.

I completely concur with cdebel. To put it in simple terms... I've placed references/URLs to another question in this THREAD. Why on earth would I do it if email exchange has taken place? Again, you jumped at conclusion!!

Netminder: Saying to someone "Repeated violations are considered an abuse of EE's systems" mean that we have cheated, violated any rule. If you didn't mean that, then your comment was absolutely irrelevant and you didn't had to say that. So from that, i assume that you treated us as cheaters.

I was not aware that it was against Term Of Use to post links to other web sites, especially when this site explain the basics of what a user is trying to implement but doesn't have the knowledge to program it himself. For example, the link that ExpExchHelp posted about Wiki. I don't consider it offensive but strictly speaking, it's going against the Term Of Use according to what you said. But i do agree that if the link lead to the solution (and nothing to clarify the question), then yes, Link should not be used because it often lead to deleted thread in other forums and that would cause some frustration to your users who are looking for that answer.

The only thing that i can suggest is to point out who this notice is for next time.
Also, try to point out the problem itself, if you have proofs of course or enough elements for suspicions. Because like i said, if you follow every comments of this thread, you will notice that he asked for my help here many times (to check at other threads that he created here). If he would have emailed them to me, he wouldn,t have posted them here (make sense?)... so your comment about emailing each other was just irrelevant.

Now that you throw up that comment about academic stuff, that can piss you off and i understand. I've noticed nothing here that could have made me think that it was academic. In fact, i didn't really thought about what could make me think of which comment in a question could make me feel like it's an academic question. So if you have stuff to talk to each other, then fine... but try to specify who you are talking to instead of firing at will blindly.

And about "Ask a related question", i've never noticed that option until you pointed that in your last comment. I'll probably use it so thanks for the info.

And yes, i've chatted with the customer support, and for your info, yes i'm paying... no mather if i've got the premium status or not, i'm still beeing billed. I think that the premium status is only there to say: "You got enough point to stop paying"... but as soon as you stop answering question, you get billed.

Holy camolie... a can of worms has been opened. Not sure if I can/want to read all of the "essays". 8)

0

Featured Post

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples. You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why tâ€¦

Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a â€¦

The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor anâ€¦

The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relatâ€¦