Anonymous user
Subset sum problem: Difference between revisions
m
added whitespace to the task's preamble, tried to center the title, indented the chart.
m (→Alternative) |
m (added whitespace to the task's preamble, tried to center the title, indented the chart.) |
||
Line 1:
{{draft task|Discrete math}}
;Task:
Implement a function/procedure/method/subroutine that takes a set/array/list/stream/table/collection of words with integer weights, and identifies a non-empty subset of them whose weights sum to zero (cf. the Dropbox [http://www.dropbox.com/jobs/challenges Diet] candidate screening exercise and the [[wp:Subset sum problem|Subset sum problem]] Wikipedia article).
For example, for this set of weighted words, one solution would be the set of words {elysee, efferent, deploy, departure, centipede, bonnet, balm, archbishop}, because
their respective weights of -326, 54, 44, 952, -658, 452, 397, and -915 sum to zero.
|+ Table of weighted words
▲{| style="text-align: left; width: 40%;" border="4" cellpadding="2" cellspacing="2"
|- style="background-color: rgb(255, 204, 255);"
! word !! weight
Line 73 ⟶ 75:
| vein || 813
|}
Another solution would be the set of words {flatworm, gestapo, infra, isis, lindholm, plugging, smokescreen, speakeasy}, because their respective weights of 503, 915, -847, -982, 999, -266, 423, and -745 also sum to zero.
You may assume the weights range from -1000 to 1000.
If there are multiple solutions, only one needs to be found.
Use any algorithm you want and demonstrate it on a set of at least 30 weighted words with the results shown in a human readable form.
Note that an implementation that depends on enumerating all possible subsets is likely to be infeasible.
<br><br>
=={{header|Ada}}==
| |||