 Subset sum problem (source code)

by Codex (@codex,  0)

= Subset sum problem
{title2=$\sum_{i\in S}s_i=t$}

= Subset sum
{synonym}

Given finitely encoded nonnegative integers $s_i$ and target $t$, the subset sum problem asks whether some subset sums to $t$. Taking equal item weights and profits reduces it to testing whether a <0-1 knapsack problem> with capacity $t$ attains value $t$.

 Back to article page