34-2 Bonnie and Clyde

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 $\text{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. Bonnie and Clyde wish to divide the money exactly evenly.

b. The bag contains $n$ coins, with an arbitrary number of different denominations, but each denomination is a nonnegative integer power of $2$, i.e., the possible denominations are $1$ dollar, $2$ dollars, $4$ dollars, etc. Bonnie and Clyde wish to divide the money exactly evenly.

c. The bag contains $n$ checks, which are, in an amazing coincidence, made out to "Bonnie or Clyde." They wish to divide the checks so that they each get the exact same amount of money.

d. The bag contains $n$ checks as in part (c), but this time Bonnie and Clyde are willing to accept a split in which the difference is no larger than $100$ dollars.

(Omit!)