Optimal Use Of Container Space

There is a number of items in varying sizes and a fixed container size.

You want to put all items into few containers as possible.

It is obviously a common problem with existing algorithms but i don't know what they are called. Some references would be nice.

-- AndreKuehne?

This is the "knapsack problem". It is NpComplete, so pragmatically one must use algorithms that yield approximate solutions, rather than optimal solutions. Googling will find vast amounts of material.

After some more research i found that the exact problem is known as BinPacking? -- AndreKuehne?

Oh yeah, I forgot that terminology. In that case, googling finds more. Here are two programs that address that:

http://www.lecad.uni-lj.si/~leon/software/colapse-backup/ http://bisqwit.iki.fi/source/jaa3.html

Also apparently there's a large "file system browser" app that does this as one of a zillion interactive features:

http://www.lns.cornell.edu/public/COMP/info/git/git_toc.html#TOC26

It mentions that, worst case, no known approximation "can guarantee a solution better than `(11/9) * OPTIMAL + 4'"

delete (thanks for the help)

Wait a second, can you tell us the application you're solving? Just curious, it might be interesting.

I am currently archiving a lot of data and just wanted to extend my burning scripts so i don't have to worry about _how_ to burn what i want to save. My aim is simply to split-up one directory into several directories of a limited size.

To make things a little more interesting: I would like a solution where the lexical order of files (putting files whose names directly follow each other on the same media) will be discarded only if the amount of saved space is above a given minimum.

But since the involved sizes are one-dimensional i guess my problem isn't that interesting as the title might suggest ;)

-- AndreKuehne?

It's still an NP-hard problem. The problem you're talking about solving is one where I've wanted a script to approximately solve in the past. I wonder if it's been done and is available out there somewhere, e.g. freshmeat.net

Since i didn't find any useful implementations, i wrote something myself this afternoon. I guess the algorithm is pretty naive, but it does the job at hand quite well.

If someone is interested in trying out or improving the script: http://akue.gmxhome.de/splitFolder/splitFolder.py.txt

At this point it does not change the folder itself, but prints the filenames in a grouped form to stdout.

-- AndreKuehne?

Algorithms like this are also useful in implementing MemoryManager?s, such as malloc(). IIRC, the only reasonable alternatives are FirstFit?, BestFit?, or WorstFit?. If a request is received that the MemoryManager? can't fulfill, try some compaction algorithm to see if it can free up enough memory for the request.

-- PaulMiller

This is similar to a MemoryManager? (although it doesn't know a priori what all the request sizes will be). You might try segregated free lists too (basically a first fit variant where you break the blocks based on the size).