• ### Popular Now

• 12
• 10
• 10
• 13
• 10

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

## 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 on other sites

Someone pointed me towards the knapsack problem

Knapsack is the algorithm which finds "take N items of highest total value"

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 finding all combinations.

##### Share on other sites

[quote name='Shruubi' timestamp='1312641314' post='4845431']
Someone pointed me towards the knapsack problem

Knapsack is the algorithm which finds "take N items of highest total value"

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 finding all combinations.
[/quote]

edit: code tags are screwing around with my formatting.

this is my current effort in c++: http://codepad.org/EQUtrrGc

that is my current effort, i'm not quite sure about how to approach my next step.

##### 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
 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.SlotSIze < 0) break;// all container is full else { // insert the object objectcontainer.insert(object); slotsleft-=object.SlotSIze; } } 

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.