Anonymous user
Talk:Subset sum problem: Difference between revisions
→task clarification: removed my question. -- ~~~~
(added a new section. -- ~~~~) |
(→task clarification: removed my question. -- ~~~~) |
||
Line 6:
: 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. --[[User:Sluggo|Sluggo]] 01:05, 3 January 2012 (UTC)
|