Algorithm searched

Ruby
1

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 ?

Keep rubying!
mcc

duck.quak

2

Meino Christian C. wrote:

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

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
3

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

4

Meino Christian C. [email protected] 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/bestfit.html) 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.

5

From: Yohanes S. [email protected]
Subject: Re: Algorithm searched …
Date: Sun, 9 Jul 2006 04:34:24 +0900

Hi Yohanes !

Thank you very much fior your reply and your program! :slight_smile:
Nice to know, that others Rubyist has same problems.
Far nicer to know, that they have already solved the problem,
hahahaha !

In another thread in this mailinglist there is a discussion why to
prefer Ruby.

The friendly replies to my initial posting are the expression of one
BIG reason (at least for me) for that.

Have a nice weekend ! :slight_smile:
mcc