To: Jerry Yu... Re: [ale] 2 Perl questions ?

[Jason Day]

On Wed, Dec 15, 2004 at 11:02:22AM -0600, Aditya Srinivasan wrote:
> The algorithm to separate files into groups <=650 sounds non trivial.
> 
> 1.List files and sizes
> 2.Sort
> 3.Pick appropriate combinations from the list (The hard part ??)
> 
> Is anyone aware of an algorithm which analyzes this sort of problem and 
> solves it ?

Yes.  It's been a while since my CS algorithms course, but I believe
this is known as the knapsack problem.  I think the general knapsack
problem is NP complete, but it can be partitioned in such a way that you
could solve this particular problem using dynamic programming.

A quick google search turns up this page, which might provide some
useful pointers:

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE145.HTM

HTH,
Jason
-- 
Jason Day                                       jasonday at
http://jasonday.home.att.net                    worldnet dot att dot net
 
"Of course I'm paranoid, everyone is trying to kill me."
    -- Weyoun-6, Star Trek: Deep Space 9