# Algorithm searched **URL:** \ **Category:** Ruby\ **Created:** [July 8, 2006, 7:32pm UTC](https://www.ruby-forum.com/t/algorithm-searched/97619 "2006-07-08T19:32:54Z")\ **Posts on this page:** 5\ **Page:** 1
**Author:** ![Meino\_Christian\_C](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/7993a0/32.png) [@Meino\_Christian\_C](https://www.ruby-forum.com/u/Meino_Christian_C)\ **Post date:** [July 8, 2006, 7:32pm UTC](https://www.ruby-forum.com/t/algorithm-searched/97619/1 "2006-07-08T19:32:54Z")
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 ---
**Author:** ![Meino\_Christian\_C](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/7993a0/32.png) [@Meino\_Christian\_C](https://www.ruby-forum.com/u/Meino_Christian_C)\ **Post date:** [July 8, 2006, 8:37pm UTC](https://www.ruby-forum.com/t/algorithm-searched/97619/2 "2006-07-08T20:37:12Z")
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 > **[Knapsack problem](https://en.wikipedia.org/wiki/0/1_knapsack_problem)** > > The knapsack problem is the following problem in combinatorial optimization: > It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. > The knapsack problem has been studied for more than a century, with early works dating ... 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 ``` ---
**Author:** ![Meino\_Christian\_C](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/7993a0/32.png) [@Meino\_Christian\_C](https://www.ruby-forum.com/u/Meino_Christian_C)\ **Post date:** [July 8, 2006, 9:21pm UTC](https://www.ruby-forum.com/t/algorithm-searched/97619/3 "2006-07-08T21:21:44Z")
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 ---
**Author:** ![Meino\_Christian\_C](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/7993a0/32.png) [@Meino\_Christian\_C](https://www.ruby-forum.com/u/Meino_Christian_C)\ **Post date:** [July 8, 2006, 9:35pm UTC](https://www.ruby-forum.com/t/algorithm-searched/97619/4 "2006-07-08T21:35:59Z")
Meino Christian C. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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](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. ---
**Author:** ![Meino\_Christian\_C](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/7993a0/32.png) [@Meino\_Christian\_C](https://www.ruby-forum.com/u/Meino_Christian_C)\ **Post date:** [July 8, 2006, 9:42pm UTC](https://www.ruby-forum.com/t/algorithm-searched/97619/5 "2006-07-08T21:42:30Z")
From: Yohanes S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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! 🙂 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 ! 🙂 mcc