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

[Aditya Srinivasan]

On Wed, 15 Dec 2004, Jason Day wrote:

> 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

Its been a while for me too which is why it interests me :)

http://www.nist.gov/dads/HTML/knapsackProblem.html
******************************************************************
Definition: Given items of different values and volumes, find the most 
valuable set of items that fit in a knapsack of fixed volume. 
******************************************************************

They seem similar but I believe this problem is slightly different. I 
can't immediately see a way to generalize it as a knapsack problem.


-- 
Thanks,
sriad