In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem. The problem can be solved using dynamic programming when the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible. Suppose the input to the algorithm is a multiset S {\displaystyle S} of cardinality N {\displaystyle N} :
S = {x1, ..., xN} Let K be the sum of all elements in S. That is: K = x1 + ... + xN. We will build an algorithm that determines whether there is a subset of S that sums to ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } . If there is a subset, then:
if K is even, the rest of S also sums to ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor }
if K is odd, then the rest of S sums to ⌈ K / 2 ⌉ {\displaystyle \lceil K/2\rceil } . This is as good a solution as possible. e.g.1 S = {1, 2, 3, 5}, K = sum(S) = 11, K/2 = 5, Find a subset from S that is closest to K/2 -> {2, 3} = 5, 11 - 5 * 2 = 1 e.g.2 S = {1, 3, 7}, K = sum(S) = 11, K/2 = 5, Find a subset from S that is closest to K/2 -> {1, 3} = 4, 11 - 4 * 2 = 3
Recurrence relation We wish to determine if there is a subset of S that sums to ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } . Let:
p(i, j) be True if a subset of { x1, ..., xj } sums to i and False otherwise. Then p( ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } , N) is True if and only if there is a subset of S that sums to ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } . The goal of our algorithm will be to compute p( ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } , N). In aid of this, we have the following recurrence relation:
p(i, j) is True if either p(i, j − 1) is True or if p(i − xj, j − 1) is True p(i, j) is False otherwise The reasoning for this is as follows: there is some subset of S that sums to i using numbers
x1, ..., xj if and only if either of the following is true:
There is a subset of { x1, ..., xj−1 } that sums to i; there is a subset of { x1, ..., xj−1 } that sums to i − xj, since xj + that subset's sum = i.
The pseudo-polynomial algorithm The algorithm consists of building up a table of size ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } by N {\displaystyle N} containing the values of the recurrence. Remember that K {\displaystyle K} is the sum of all N {\displaystyle N} elements in S {\displaystyle S} . Once the entire table is filled in, we return P ( ⌊ K / 2 ⌋ , N ) {\displaystyle P(\lfloor K/2\rfloor ,N)} . Below is a depiction of the table P {\displaystyle P} . There is a blue arrow from one block to another if the value of the target-block might depend on the value of the source-block. This dependence is a property of the recurrence relation.
function can_be_partitioned_equally(S) is input: A list of integers S. output: True if S can be partitioned into two subsets that have equal sum.
n ← |S| K ← sum(S) P ← empty boolean table of size ( ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } + 1) by (n + 1)
initialize top row (P(0,x)) of P to True initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
for j from 1 to n for i from 1 to ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor }
x = S[j-1] if (i-x) >= 0 then P(i, j) ← P(i, j-1) or P(i-x, j-1) else P(i, j) ← P(i, j-1)
return P( ⌊ K / 2 ⌋ {\displaystyle \lfloor K/2\rfloor } , n)
Example Below is the table P for the example set used above S = {3, 1, 1, 2, 2, 1}:
… excerpt ends here. Continue reading the full article.
