   Finding the best combination algorithm issues
  I'm working on a card game and I need to figure out an algorithm for buying cards but I am completely stuck.The way it works is the player can have in their hand at any time any combination of cards of values 1, 2, or 3 and can use said cards to buy cards costing from 2-8. The problem is that the algorithm needs to select which cards to use to buy the cards by using the lowest possible value of cards.For example, if the player has 112 in their hand and is buying a card that costs 2 then we would use 11 to buy it instead of the 2.Also, whenever possible it needs to match the cost exactly. Going over is allowed but should be avoided if possible.any ideas or hints? I've been stuck on this for hours now and am not getting anywhere.   
  Sort the hand by value and then apply a greedy algorithm to chew through cards until you match the cost? This seems to be a rather straight forward approach.   ;Quote:Original post by bobofjoeSort the hand by value and then apply a greedy algorithm to chew through cards until you match the cost? This seems to be a rather straight forward approach.If I had any idea what a greedy algorithm was then it might be :) Care to elaborate or link to an example or something? I've never heard of that before   ;  This sounds like a homework problem, so I won't give too much help.  I will however answer your question about greedy algorithms.  I'll also point out a problem with bobofjoe's answer.You have a number of choices to make in a sequence.  Greedy algorithms are those that make the "obvious" choice at each step without considering how this choice will affect what you can do at future steps.  A greedy algorithm for finding the shortest path between two points in a maze of rectangular tiles might, at each step, look at the adjacent tiles, and move to whichever one is closest to the goal -- even if that takes you down a dead end.What bobofjoe is saying (I think) is that you could, 1 - sort your hand 2 - spend cards, starting at low cards, until you've paid the required amount.This will not always give you the correct result.  For instance, say you have the hand, "1 1 1 3 3" and want to buy a 4.  With this algorithm you'd spend your first one, then your second one, and then your third one.  At this point you'd only be up to 3 which is less than your goal of 4, so you'd also then spend a 3.  Then you'd have spent enough so you'd stop, having spent "1 1 1 3."  But you could have gotten away with spending just "1 3."Finally, I think that you need to specify the problem a little more carefully.  There are some conflicting requirements, and it's not clear how they should be prioritized.   ;  Never mind, I looked it up on Wikipedia and was able to figure out a way to make a greedy algorithm that works :) Thanks a ton for the help though. I would have never figured it out otherwise.   