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

[attriel at d20boards.net (attriel)]

> 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.

I always learned it as the box-packing algorithm, which is NP-complete
only as regards an "optimal" solution.

As long as non "optimal" is acceptable, geoff's solution should work, or
just:

Total size/media size
Sort by size.
Add files to "media" as they fit.  Largest into first "media", second
largest into first if it fits still, else it goes to second.  Third tries
first, tries second, goes to third, etc.

Non-optimal probably, and not the most "efficient" manner, but it'll work,
and I don't imagine it would be too bad.  You could also set it to keep
directories together "when possible" (IE -- when you go through the full
"media" list and you can't fit the dir anymore, break it and do it
file-by-file)

--attriel