[no subject]

> 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:
> 
&gt; <a  rel="nofollow" href="http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE145.HTM";>http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE145.HTM</a>

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

<a  rel="nofollow" href="http://www.nist.gov/dads/HTML/knapsackProblem.html";>http://www.nist.gov/dads/HTML/knapsackProblem.html</a>
******************************************************************
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


</pre>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<hr>
<!--X-Follow-Ups-End-->
<!--X-References-->
<ul><li><strong>References</strong>:
<ul>
<li><strong><a name="00545" href="msg00545.html">To: Jerry Yu...     Re: [ale] 2 Perl questions ?</a></strong>
<ul><li><em>From:</em> jasonday at worldnet.att.net (Jason Day)</li></ul></li>
</ul></li></ul>
<!--X-References-End-->
<!--X-BotPNI-->
<ul>
<li>Prev by Date:
<strong><a href="msg00545.html">To: Jerry Yu...     Re: [ale] 2 Perl questions ?</a></strong>
</li>
<li>Next by Date:
<strong><a href="msg00547.html">To: Jerry Yu...     Re: [ale] 2 Perl questions ?</a></strong>
</li>
<li>Previous by thread:
<strong><a href="msg00545.html">To: Jerry Yu...     Re: [ale] 2 Perl questions ?</a></strong>
</li>
<li>Next by thread:
<strong><a href="msg00549.html">To: Jerry Yu...     Re: [ale] 2 Perl questions ?</a></strong>
</li>
<li>Index(es):
<ul>
<li><a href="maillist.html#00546"><strong>Date</strong></a></li>
<li><a href="threads.html#00546"><strong>Thread</strong></a></li>
</ul>
</li>
</ul>

<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
</body>
</html>