From: Robert Klemme <shortcutter@...>
Date: 2006-07-09T03:35:13+09:00
Subject: Re: Algorithm searched ...

Meino Christian Cramer wrote:
> Hi,
> 
>  I was thinking of a "problem" I have:
>  On my harddisc there are several recording of broadcasts made with my
>  DVB-T receiver. Let it be an amount of 20 or so.
> 
>  Each recording is about 1.2GB - 3.5GB in size.
> 
>  An DVD takes 4.7GB of data.
> 
>  I am looking for a way to choose those combinations of recordings,
>  that the space on the DVDs are used best -- or in other words: that
>  as less DVDs are needed to store all recordings.
> 
>  It may be that this is equivalent to the "backpacker's problem" --
>  for which -- as far as I know -- is no algorithm available. So I am
>  should better say: I am looking for a way to find those combinations
>  a fast way of attempts as for an exact algorithm, which is proofen to
>  solve the problem...but...I have not studied computer science...so...
> 
>  How can I do such in Ruby best ?

This is known as "knapsack problem": see for example
http://en.wikipedia.org/wiki/0/1_knapsack_problem

There are algorithms but they are in NP, i.e. they perform worse than 
polynomial.  In your case (20 - 30) they might still yield acceptable 
runtime (compared to the time needed to burn the DVD).

IIRC another approach to solve this are genetic algorithms.

Kind regards

	robert