'Subset Sum' music tape application

This applet demonstrates a practical application of the subset sum NP-Complete problem.

This 40-track version uses the same engine as the 20-track version. It finds a correctly summing subset in a similarly short time. By substituting values higher than the tape length, You can thin out the density of qualifying combinations to the extent that it would take hundreds of hours. So as not to leaving the applet hanging, it gives up after 1 million iterations.

 

 

Here is a version of the applet with 20 of the tracks set to high values. Try adding a few more to see it really begin to struggle. I've raised the limit to 5 million for this one.

 

 

Return to main page.