What sorting algorith does something like this?

[Kyteland]

I was given a problem where I need to sort a set of weighted elements in to the minimum number of fixed sized containers. I remember doing something like this for a class in school, but I can't remember how.

So imagine that you have a pile of coins and that those coins can may have any value less than $1.00. I want something to sort those coins in to piles with a value of $1.00 or less. I need a way to minimize the number of piles produced during sorting.

My firt thought was something like the traveling salesman problem, but that isn't right. I can't think of anything else.

If you can think of something that is listed in Introduction to Algorithms that would be great because I have the book in front of me.

Edit: Found the solution. Thanks everyone.
http://en.wikipedia.org/wiki/Bin_packing_problem

 

[HardcoreRobot]

im not going to think about this enough to give a good answer, but look into the Knapsack Problem.

 

[Whitecloak]

Originally posted by: Kyteland
I was given a problem where I need to sort a set of weighted elements in to the minimum number of fixed sized containers. I remember doing something like this for a class in school, but I can't remember how.

So imagine that you have a pile of coins and that those coins can may have any value less than $1.00. I want something to sort those coins in to piles with a value of $1.00 or less. I need a way to minimize the number of piles produced during sorting.

My firt thought was something like the traveling salesman problem, but that isn't right. I can't think of anything else.

If you can think of something that is listed in Introduction to Algorithms that would be great because I have the book in front of me.

linear programming.

 

[Kyteland]

Originally posted by: whitecloak
linear programming.

It's looking like a dynamic programmin problem, but I'll look at that too. Thanks.