Anonymous user
Subset sum problem: Difference between revisions
Show a non-brute-force Mathematica solution.
({{Out}}) |
(Show a non-brute-force Mathematica solution.) |
||
Line 778:
A zero-sum subset of length 4 : {brute,centipede,efferent,plugging}
....</pre>
The above code uses a brute-force approach, but Mathematica includes several solution schemes that can be used to solve this problem. We can cast it as an integer linear programming problem, and thus find the largest or smallest subset sum, or even sums with specific constraints, such as a sum using three negative values and nine positive values.
<lang Mathematica>a = {{"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}};
desiredValue = 0;
aNames = #[[1]] & /@ a;
aValues = #[[2]] & /@ a;
aOnes = ConstantArray[1, Length[a]];
aZeroOnes = ConstantArray[{0, 1}, Length[a]];
Off[LinearProgramming::lpip];
maxSoln =
LinearProgramming[-aOnes, {aValues}, {{desiredValue, 0}}, aZeroOnes, Integers];
Print["Maximal solution: ", Select[Transpose[{maxSoln*aValues, aNames}], #[[1]] != 0 &]];
minSoln =
LinearProgramming[
aOnes, {aValues, aOnes}, {{desiredValue, 0}, {1, 1}}, aZeroOnes, Integers];
Print["Minimal solution: ", Select[Transpose[{minSoln*aValues, aNames}], #[[1]] != 0 &]];
threeNineSoln =
LinearProgramming[
aOnes, {aValues,
Boole[# < 0] & /@ aValues,
Boole[# > 0] & /@ aValues},
{{desiredValue, 0}, {3, 0}, {9, 0}}, aZeroOnes, Integers];
Print["3 -ves, 9 +ves: ", Select[Transpose[{threeNineSoln*aValues, aNames}], #[[1]] != 0 &]];
</lang>
<pre>Maximal solution: {{-624, alliance}, {-915, archbishop}, {397, balm},
{870, brute}, {-658, centipede}, {362, cobol}, {590, covariate},
{44, deploy}, {645, diophantine}, {54, efferent}, {-326, elysee},
{376, eradicate}, {-983, exorcism}, {170, fiat}, {-874, filmy},
{503, flatworm}, {915, gestapo}, {-847, infra}, {-982, isis},
{999, lindholm}, {-880, mincemeat}, {756, moresby}, {183, mycenae},
{-266, plugging}, {423, smokescreen}, {-745, speakeasy}, {813, vein}}
Minimal solution: {{-915, archbishop}, {915, gestapo}}
3 -ves, 9 +ves: {{-915, archbishop}, {397, balm}, {452, bonnet},
{362, cobol}, {44, deploy}, {54, efferent}, {-983, exorcism},
{170, fiat}, {503, flatworm}, {-982, isis}, {475, markham},
{423, smokescreen}}.</pre>
=={{header|OCaml}}==
| |||