Shruubi 102 Report post Posted August 6, 2011 I do apologize first off if this has been posted in the wrong section, i was unsure as to where a question like this should go, and thought this board would be most appropriate. My problem is this: Given an input of X, I need to find all the possible ways I can buy X amount of items given X amount of dollars (given that the prices for the items are constants: 2, 7 and 0.5). Someone pointed me towards the knapsack problem, however all the material I have found on the subject is a little hard to decipher let alone translate from so that it works for price and not weight, and that the knapsack problem only provides one output. The only other solutions I have come across have been on maths websites which present the same problem, but give the explanation for only one input and in such a way as it seems near impossible to translate the explanation for a more general input. Any hints or guidance would be greatly appreciated. Thanks. 0 Share this post Link to post Share on other sites
Antheus 2409 Report post Posted August 6, 2011 [quote name='Shruubi' timestamp='1312641314' post='4845431'] Someone pointed me towards the knapsack problem[/quote] Knapsack is the algorithm which finds "take N items of highest total value" [quote] I need to find all the possible ways I can buy X amount of items given X amount of dollars[/quote] Iterate over all possible combinations (not permutations), print those where total value of selected items is <= X. The problem now becomes [url="http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n"]finding all combinations[/url]. 0 Share this post Link to post Share on other sites
Shruubi 102 Report post Posted August 6, 2011 [quote name='Antheus' timestamp='1312642771' post='4845439'] [quote name='Shruubi' timestamp='1312641314' post='4845431'] Someone pointed me towards the knapsack problem[/quote] Knapsack is the algorithm which finds "take N items of highest total value" [quote] I need to find all the possible ways I can buy X amount of items given X amount of dollars[/quote] Iterate over all possible combinations (not permutations), print those where total value of selected items is <= X. The problem now becomes [url="http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n"]finding all combinations[/url]. [/quote] edit: code tags are screwing around with my formatting. this is my current effort in c++: [url="http://codepad.org/EQUtrrGc"]http://codepad.org/EQUtrrGc[/url] that is my current effort, i'm not quite sure about how to approach my next step. 0 Share this post Link to post Share on other sites
smasherprog 568 Report post Posted August 6, 2011 One way to solve the problem . . . . . . . while this not always optimal, it should be close to it Say you have a bag that has 50 slots and you have a bunch of random sized objects. Sort the random objects by size, using quicksort this is a fast operation. Then, start inserting the sorted objects into your container keeping track of how many slots are left. psudo code [code] vector<objectstobeinserted> objects; vector<objectcontainer> objectcontainer; sort objects by size using quicksort least to greatest const int containersize = 50; int slotsleft = containersize; for( size_t i(0); i< objects.size(); i++ ){ if(slotsleft - object[i].SlotSIze < 0) break;// all container is full else { // insert the object objectcontainer.insert(object[i]); slotsleft-=object[i].SlotSIze; } } [/code] The other way is optimal, but after sorting the objects, you have to iterate over the objectsttobeinserted starting at the smallest until you find an object that will not fit. Once you find that one, that will be your beginning. You start going backwards from the one you found that wouldn't fit inserting if it will fit until you hit the beginning of the array. 0 Share this post Link to post Share on other sites