Sign in to follow this  

algorithm for buying items

This topic is 2324 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
[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].

Share this post


Link to post
Share on other sites
[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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 2324 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this