Partition Problems Ive read on wikipedia that partition prob

Partition Problems:

I’ve read on wikipedia that partition problems are considered NP-Complete, but in the solution page for the book ‘Introduction to Algorithms’ there was a description of an algorithm that solves the below problem in Polynomial time. What I don’t understand is how could they solve it if it’s NP-Complete ? Or it is easier to partition if the coin set has only 2 denominations ?

Bonnie and Clyde have just robbed a bank. They have a bag of money and want to divide it up. For each of the following scenarios, either give a polynomial-time algorithm, or prove that the problem is NP-complete. The input in each case is a list of the n items in the bag, along with the value of each.
a. The bag contains n coins, but only 2 different denominations: some coins are worth x dollars, and some are worth y dollars. Decide if Bonnie and Clyde can divide the money exactly evenly.

Solution

The problem will be solved mistreatment dynamic programming once the dimensions of the set and also the size of the total of the integers within the set don\'t seem to be too huge to render the storage needs impossible.

Suppose the input to the rule may be a list of the form:

S = x1, ..., xn
Let N be the quantity of components in S. Let K be the total of all components in S. That is: K = x1 + ... + xn. we\'ll build associate degree rule that determines if there\'s a set of S that sums to \\lfloor K/2 \ floor . If there\'s a set, then:

if K is even, the remainder of S additionally sums to \\lfloor K/2 \ floor
if K is odd, then the remainder of S sums to \\lceil K/2 \ ceil . this can be nearly as good an answer as doable.
Recurrence relation[edit]
We would like to see if there\'s a set of S that sums to \\lfloor K/2 \ floor . Let:

p(i, j) be True if a set of sums to i and False otherwise.
Then p( \\lfloor K/2 \ floor , n) is True if and as long as there\'s a set of S that sums to \\lfloor K/2 \ floor . The goal of our rule are going to be to work out p( \\lfloor K/2 \ floor , n). In aid of this, we\'ve got the subsequent return 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 fake otherwise
The reasoning for this can be as follows: there\'s some set of S that sums to i mistreatment numbers

x1, ..., xj
if and as long as either of the subsequent is true:

There is a set of that sums to i;
there is a set of that sums to i xj, since xj + that subset\'s total = i.
The pseudo-polynomial algorithm[edit]
The rule is to make up a table of size \\lfloor K/2 \ floor by n containing the values of the return. keep in mind K is that the size of the total, whereas N is that the variety of components. Once the complete table is crammed in, come back P( \\lfloor K/2 \ floor , n). Below may be a image of the table P. there\'s a blue arrow from one block to a different if the worth of the target-block may rely on the worth of the source-block. This dependence may be a property of the return relation.