Question

Ramya has two children. One day she gave them a jigsaw puzzle and said that if they solved the puzzle together, then she will let them take the money from the piggy bank to buy snacks that they like. Children became happy and they spent two hours solving the jigsaw puzzle. As promised Ramya opened the piggy bank and to be fair, she divided the money between the children such a way that the difference between the money that each children got was the minimum.

Requirements:
1. Formulate an efficient recursive algorithm using Dynamic programming to divide the money as equal as possible

Answer 1

A dynamic programming solution involves creating a recursive algorithm that selects subsets of money amounts to minimize the difference between the sums given to each child, optimizing the process by storing results of subproblems.

Step-by-step explanation:

The challenge presented is to devise an efficient recursive algorithm using dynamic programming to ensure the even division of money. To achieve a fair division, we need to minimize the difference between the amounts each child receives. Dynamic programming is suitable for solving this optimization problem because it breaks down a complex problem into simpler subproblems and stores the results of these subproblems to avoid redundant calculations.

In this specific case, you would use dynamic programming to find the subset of money amounts that come closest to half of the total sum in the piggy bank. If we denote the set of money amounts as M, and the total sum as S, we aim to find a subset M' of M such that the sum of M' (denoted as sum(M')) is as close as possible to S/2. The minimum difference would be |2*sum(M') - S|.

Recursively, the function would decide for each amount of money whether to include it in M' or not. The base cases would be when no items are left or when the sum of the selected items reaches half of the total sum. To optimize this, we would use a two-dimensional array to store the results of subproblems, where the first dimension represents the number of items considered, and the second dimension represents the current sum. This array is then used to avoid recalculating the same subproblems, thus reducing the time complexity significantly.

Implementing this dynamic programming approach ensures that the end result is having the smallest possible difference between the two sums each child gets, fulfilling the mother's condition of fairness.