Solution Found!
Bonnie and Clyde Bonnie and Clyde have just robbed a bank.
Chapter 34, Problem 34-2(choose chapter or problem)
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 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.
Questions & Answers
QUESTION:
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 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.
ANSWER:Step 1 of 4
a)
Assume that there are 
Then the total amount is 
Note that Bonnie can either take 0 coin worth x dollars, or 1 coin worth x dollars, or 2 coins worth x dollars, or at most m coins worth x dollars. Since there are only two, we can just check after Bonnie takes coins worth x dollars, if coins worth dollars can make up the rest of the amount.
For example, if Bonnie takes no coins worth x dollars, then check if S/2 mod y and if
