[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Algorithm searched ...

Meino Christian Cramer

7/8/2006 5:27:00 PM

4 Answers

Robert Klemme

7/8/2006 6:32:00 PM

0

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

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

Marcin Mielzynski

7/8/2006 7:19:00 PM

0

Robert Klemme wrote:

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

Ant colony systems can also be considered (they are more convergent and
less susceptible to local optimas at the same time).
There are also deterministic approximate algorithms for the knapsack
problem.


lopex

Yohanes Santoso

7/8/2006 7:34:00 PM

0

Meino Christian Cramer <Meino.Cramer@gmx.de> writes:

> It may be that this is equivalent to the "backpacker's problem" --

This problem is known as the binary (0/1) knapsack problem.
There is a program called ``bestfit``
(http://oskarsapps.mine.nu/be...) that would find the optimal
solution.

I do not use that because I prefer similarly named files to be put in
a media. So, I wrote my own implementation (attached) that solved that
using greedy approximation. You can choose whether to group by name or
by size.

For my files, the grouping produced by the greedy approximation (both
by name or size) is about 90% close to the optimum grouping. It is
acceptable for me. You may find it useful.


YS.

Meino Christian Cramer

7/8/2006 7:42:00 PM

0