The 0-1 Knapsack

Tonight, I had the bright idea of putting a subset of podcasts onto my USB thumb drive. But which ones? How could I optimally get the most MP3 into a fixed amount of space without wasting any?

I sat down with my iBook and my Sedgewick and started thinking about the problem. I had about 20 lines of an algorithm down when I was pleased to discover someone had already beaten me to it by a couple of years.

Behold, partition.py, a script courtesy of Chad Austin. This little app just sits in C:\Python23\Scripts and tells me exactly what can fit on the drive without a lot of wasted space, and can even post-sort them into directories accordingly. Thanks, Chad!