Does any one have solution key for this problem: \"Bonnie and Clyde have just ro

Question

Does any one have solution key for this problem:

"Bonnie and Clyde have just robbed a bank. They have a bag of moneyand want to divide
it up. For each of the following scenarios, either give apolynomial-time algorithm, or prove
that the problem is NP-hard. Use the fact that the Subset Sumproblem is NP-hard. The
input for the Subset Sum problem are n + 1 positive integers X ={x1, . . . , xn}, L. The
output to the Subset Sum problem is 1 if there exist a subset of Xthat sums to L, and
the output is zero otherwise.
(a) There are n coins, but only 2 different denominations: somecoins are worth x dollars,
and some are worth y dollars. They wish to divide the money exactlyevenly.
(b) There are n coins, with an arbitrary number of differentdenominations, but each
denomination is a nonnegative integer power of 2, i.e., thepossible denominations are
1 dollar, 2 dollars, 4 dollars, etc. They wish to divide the moneyexactly evenly.
(c) There are n checks, which are, in an amazing coincidence, madeout to “Bonnie or
Clyde.” They wish to divide the checks so that they each getthe exact same amount
of money.
(d) There are n checks, but this time they are willing to accept asplit in which the
difference is no larger than 100 dollars."

Or at least give some hints please.

Thanks

Explanation / Answer

Dear User, a)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.