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.

0

ExpExchHelpAuthor Commented:

cdebel:

Thanks... 'much obliged.

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.

Thousand thanks in advance!!!

EEH

0

ExpExchHelpAuthor Commented:

cdebel:

Please see my previous posting first.

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?

0

ExpExchHelpAuthor Commented:

cdebel:

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

0

ExpExchHelpAuthor Commented:

cdebel:

Sorry... one more follow-up question...

If I wanted to also display/print out the respective values, weights, and volumes, but the "Total Value", how would I go about it.

I'll dabble w/ this but I just wanted to make sure I still "catch you" before you lose track of this.

Thank you,
EEH

0

ExpExchHelpAuthor Commented:

cdebel:

'Just saw your posting... man, you are truly awesome!!!!

EEH

0

ExpExchHelpAuthor Commented:

cdebel:

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

Wow... this is awesome.... I can't thank you enough for your help!!!!!

I'm going to study the code and play with other data sets (as well as compare them to Excel's solution.

Final question... how come the sorting order changed from (1, 3, 6, 10) to (3, 6, 1, 10). 'Just curious.

EEH

0

ExpExchHelpAuthor Commented:

cdebel provided EXCELLENT HELP in this question.

I truly appreciate the support and patience that was provided to me.

This makes the EE forum truly the best place on the web!!!

0

ExpExchHelpAuthor Commented:

cdebel:

The last/final question may have gotten "lost" to the other comment.

How come the sorting order changed from (1, 3, 6, 10) to (3, 6, 1, 10). 'Just curious.

EEH

0

ExpExchHelpAuthor Commented:

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

0

ExpExchHelpAuthor Commented:

cdebel:

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'm just a bit baffled... any final suggestions?

EEH

0

ExpExchHelpAuthor Commented:

cdebel:

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.

0

ExpExchHelpAuthor Commented:

cdebel:

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.

EEH

0

ExpExchHelpAuthor Commented:

cdebel:

Got it... that's a big improvement (total value of 1805). I also like the "Tableau des ratios". That's definitely a "keeper". 8)

As mentioned, I'll do more research on the "local search". I'll keep you posted.

EEH

0

ExpExchHelpAuthor Commented:

Sorry... one more quick one.

Per snapshot below... how do I include rounding to two decimals?

I do computer programming for living, but i've not used this language for years.

I mainly use C#, VB.NET, and ASP.NET at the moment.

I've not used C++, COBOL and some other languages since years.

Just to give you an idea: i knew there was a command "COUT" to display some text, and PRINTF... but i didn't remembered how to use them.

0

ExpExchHelpAuthor Commented:

cdebel:

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!

0

ExpExchHelpAuthor Commented:

cdebel:

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.

0

ExpExchHelpAuthor Commented:

cdebel:

Good advice... based on your recommendations, I'll attempt to come up w/ a structure on the Local Search.

Will keep you posted.

Thanks again for the hints earlier.

EEH

0

ExpExchHelpAuthor Commented:

cdebel:

I'm trying to pass the computed values from the function"Greedy" to "LocalSearch". See code below.

I'm not sure if I used the proper method/syntax. Right now, the cout statement "This is a test!" does NOT print.

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

If you got any request, please check at my profile. You can email me if you need me to check at one of your question.

We shouldn't use this thread anymore, it's closed and we are "poluting" this answer.

0

ExpExchHelpAuthor Commented:

cdebel:

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.

Netminder: Have you tried to email me this morning? LMAO :-)

0

ExpExchHelpAuthor Commented:

Netminder:

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!!

EEH

0

ExpExchHelpAuthor Commented:

cdebel:

No, I actually sent out the email with a reference to another question. My bet if what was confusing.

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.

0

ExpExchHelpAuthor Commented:

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

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

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.