Two robbers come up with a scheme to rob a bank. Their getaway plan depends on d

Question

Two robbers come up with a scheme to rob a bank. Their getaway plan depends on dividing their loot as quickly as possible and then going their separate ways. Clearly, each robber wants an equal portion of the loot. As they grab items from the bank safe they stamp an estimated value on each item. They have asked you for an algorithm that will divide the loot as quickly as possible. The robbers are pretty sure that there is a way to divide the loot equitably but if this is not the case they have decided to abandon the venture altogether and leave all the loot behind.

1)Recursive/optimal substructure for the problem. Provide the recurrence relation and an asymptotic bound.

Explanation / Answer

First we need to calculate the sum of the Array, if it is odd it is not possible to divide the item into two equal halves and they have to abandon the venture altogether and leave all the loot behind. If the sum is even, calculate sum/2 and find a subset of array with sum equal to sum/2. ecurrence relation :- isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) || boolean dp_coin_problem(int[] l,int n,int sum){ boolean[][] ans = new boolean[sum+1][n+1]; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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