You may want to check out the karp.py routine posted at http://aspn.activestate.com/ASPN/Mail/Message/python-Tutor/749797
Right now it is coded to split N numbers into 2 groups that have sums as nearly identical as possible. The set of numbers it is coded to test are are the first 50 square roots of integers; you would replace these with a list of N file sizes that are close to 2X a single disk capacity and it would tell you how to split up the group into two nearly-identically sized groups. It's "very, very, very clever, and runs in an eyeblink" says Tim Peters. You might even want to use Tim's greedy "knapsack filler" approach that he initially proposed as part of the thread above which will try random selections from a list of values and keep track of the one that came closest to a target value. Your target value would be 2X the storage limit and then you could use the karp routine to split it nicely. Tim's greedy approach is at
http://mail.python.org/pipermail/tutor/2001-August/008075.html
An alternative to breaking your list of file sizes into sublists that are close to 2X your disk capacity would be to generalize the algorithm to break the numbers into M groups rather than 2 groups...but I'm not sure how easy that will be.
You're going to love using the karp for this problem :-)
/c
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
