Subset sum problem: Difference between revisions
Content deleted Content added
m →version 1: change a word to make the OUTPUT section clearer. -- ~~~~ |
→{{header|Python}}: Brute force it |
||
Line 494: | Line 494: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Version 1=== |
|||
<lang python>words = { # some values are different from example |
<lang python>words = { # some values are different from example |
||
"alliance": -624, "archbishop": -925, "balm": 397, |
"alliance": -624, "archbishop": -925, "balm": 397, |
||
Line 538: | Line 539: | ||
('elysee', -326) |
('elysee', -326) |
||
</pre> |
</pre> |
||
===Brute force=== |
|||
<lang python>>>> from itertools import combinations |
|||
>>> |
|||
>>> word2weight = {"alliance": -624, "archbishop": -915, "balm": 397, "bonnet": 452, |
|||
"brute": 870, "centipede": -658, "cobol": 362, "covariate": 590, |
|||
"departure": 952, "deploy": 44, "diophantine": 645, "efferent": 54, |
|||
"elysee": -326, "eradicate": 376, "escritoire": 856, "exorcism": -983, |
|||
"fiat": 170, "filmy": -874, "flatworm": 503, "gestapo": 915, |
|||
"infra": -847, "isis": -982, "lindholm": 999, "markham": 475, |
|||
"mincemeat": -880, "moresby": 756, "mycenae": 183, "plugging": -266, |
|||
"smokescreen": 423, "speakeasy": -745, "vein": 813} |
|||
>>> answer = None |
|||
>>> for r in range(1, len(word2weight)+1): |
|||
if not answer: |
|||
for comb in combinations(word2weight, r): |
|||
if sum(word2weight[w] for w in comb) == 0: |
|||
answer = [(w, word2weight[w]) for w in comb] |
|||
break |
|||
>>> answer |
|||
[('archbishop', -915), ('gestapo', 915)]</lang> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |