Talk:Subset sum problem

I ran into some unanticipated implementation issues the last time I tried to create a task, so I'd like to request feedback on this one before promoting it even though it seems straightforward enough to me.

Sluggo 15:58, 1 January 2012 (UTC)

1) Why the words? 2) Caution about trying all subsets being "infeasible" seems superfulous. The problem is NP-complete, so for any algorithm, it's easy enough to construct a data set that will run (practically) forever or exhaust memory. --Ledrug 08:16, 2 January 2012 (UTC)

Thank you for your comments. My rationale is as follows. 1) Any practical application in which this calculation is needed would probably pertain to something more than just integers (e.g., the Dropbox candidate screening exercise). The words are there to stand in for whatever the integers might represent, and thereby to allow other programming language features than arithmetic to be demonstrated in the solutions. 2) Although this is an NP complete problem, an efficient implementation is possible in practice when the weights are restricted to a manageable range as stipulated (e.g., -1000 to 1000). One only needs a bit vector with an entry for each possible sum, and a linear time traversal of the word list. I wanted to make it clear that an alternative to the brute force solution exists and is appropriate. --Sluggo 01:05, 3 January 2012 (UTC)

how many solutions?

I was wondering how many solutions there are for the sample names/weights shown, so I ran my REXX program with a "stop" value of 32,000. The REXX program found that many results.
Does anyone have a fast program that could the find exact number of results (whose weights add up to zero)?
Since REXX is an interpretive language, it's not exactly a speed demon for these types of number crunching. -- Gerard Schildberger 18:03, 3 May 2012 (UTC)

Apparently there are 349167 combinations of zero sum. Considering subset sum problem is about deciding whether any combination exists at all, that does seem a little high as far as designing a task is concerned: making solutions a dime a dozen doesn't motivate people to use proper methods a difficult task deserves. --Ledrug 20:11, 3 May 2012 (UTC)

Uf-ta. I was going to put in some optimizations into the REXX program, but with over 1/3 million subsets (for solutions), I'm not going to bother. -- Gerard Schildberger 22:08, 3 May 2012 (UTC)

Well, I decided to go ahead and optimize the REXX program, and it's twice as fast. After a day of thinking, I again made it twice as fast. The brute force solution may not be appropriate (says Sluggo), but it's doable. -- Gerard Schildberger 03:51, 8 May 2012 (UTC)

Huh, "doable" is such a subjective thing. Suppose the thirty one numbers given in the task were instead these:<lang>-61 1 32 373 311 249 311 32 -92 -185 -433 -402 -247 156 125 249 32 -464 -278 218 32 -123 -216 373 -185 -402 156 -402 -61 -31 902</lang>

would it still be doable? --Ledrug 04:42, 8 May 2012 (UTC)

Yes (apart from the fact that there would be less solutions listed, but that computing time isn't much compared to the summing of the weights for the various combinations). The REXX solution I coded doesn't care what the weights are, it still adds them together to see if they sum to zero (actually, some particular target in this case which just happens to be zero). I was thinking about added some optimization --- sorting the weights in ascending order, and then taking advantage of the fact that if the sum gets "too large", the rest of the weights need not be summed, and also eliminating any outlier weights, but I didn't. As it turns out, their are no outlier weights, but still, the code couldn've been added. -- Gerard Schildberger 05:13, 8 May 2012 (UTC)

Er no, try the example above, and see how long it takes. I'm rather curious where you draw the line between "doable" and "not". --Ledrug 05:32, 8 May 2012 (UTC)

It takes as long as the original set of weights (to complete). This is how the REXX program works. Even though takes longer to find the first solution (if any), that doesn't mean that it takes a longer time to complete. As for my definition of "doable", to me means that the program can complete is a reasonable time, and "reasonable" depends just how badly I want the results (output). I've been running a program (not related to this) for over five years now because I want the output. For something this trivial (the summing of weights, albeit it consumes a lot of computer time), I won't bother. I'm using my fast computer for other things. And my main computer that I connect to the internet is just too slow (and I hate to say what century I built it). -- Gerard Schildberger 06:42, 8 May 2012 (UTC)