Talk:Subset sum problem: Difference between revisions
Content added Content deleted
(more explanation) |
(added a new section. -- ~~~~) |
||
| Line 6: | 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) |
: 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) |
||
==task clarification== |
|||
Just to clarify, when the task says to "implement a function ..., and identifies a non-empty subset ..." --- I took it to mean to identify just ONE (a) subset, but it could be interpreted to mean some or all. I would like that point to be made clear. -- [[User:Gerard Schildberger|Gerard Schildberger]] 06:13, 3 May 2012 (UTC) |
|||
Revision as of 06:13, 3 May 2012
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)
task clarification
Just to clarify, when the task says to "implement a function ..., and identifies a non-empty subset ..." --- I took it to mean to identify just ONE (a) subset, but it could be interpreted to mean some or all. I would like that point to be made clear. -- Gerard Schildberger 06:13, 3 May 2012 (UTC)