All of the interesting technological, artistic or just plain fun subjects I'd investigate if I had an infinite number of lifetimes. In other words, a dumping ground...

Wednesday, 17 October 2007

bin packing

http://facebook.enomalylabs.com/treemap7.php

This widget has been developed by Khaz Sapenov, using "bin packing" algorithm.

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, and creating file backup in removable media.

Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish results which, though very good in most cases, may not be the optimal solution. For example, the first fit algorithm provides a fast but often nonoptimal solution, involving placing each item into the first bin in which it will fit. It requires O(n log n) time. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm.


No comments:

tim's shared items

Blog Archive

Add to Google Reader or Homepage