|
'Subset Sum' music tape application This applet demonstrates a practical application of the subset sum NP-Complete problem. You can alter the 20 track times to whatever you want, and can also alter the tape length You can exclude tracks by setting them to spaces. See how few tracks are required to get the result you want. When you get down to 15, you'll see you can still make alterations to track times, without causing it serious problems. |
With just 20 tracks, there are just over one million possible combinations, so we're not in the going to blow any fuses in getting our answer, even if there happened to be just one solution.
The next applet applies the same algorithm to a set of 40 tracks. This gives us the much meatier number of 1,099,511,627,776 combinations to work through.