Anonymous user
Talk:Subset sum problem: Difference between revisions
→how many solutions?: replying to query about "doable"? -- ~~~~
(→how many solutions?: replying to query about "doable"? -- ~~~~) |
|||
Line 21:
::: 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? --[[User:Ledrug|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. -- [[User:Gerard Schildberger|Gerard Schildberger]] 05:13, 8 May 2012 (UTC)
| |||