Algorithm Analysis

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. 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.