Question

You have made a fortune in Wall Street. The IRS is suspicious and you must launder the money.
You have D dollars and you are considering all the different ways you can divide this amount (in
integer values) to n different criminal groups. Each group can take up to ai dollars without
alerting the IRS. You also have D <=a1 + a2 + .. + an. Using bottom-up dynamic programing,
write pseudo-code to determine how many different ways you can divide the D dollars. What is
the running time of your solution?

Answer 1

Answer :

We are going to use the bottom-up implementation of the dynamic programming to the code.

Our function is going to need the denomination vectors of money(d), the value for which laundering has to be made (n) and number of denominations we have (k or number of elements in the array d) i.e., MONEY-LAUNDER(d, n, k)

Let's start by making an array to store the minimum number of groups needed for each value i.e., M[n+1].

We know that for a value of 0, no groups are needed at all.

M[0] = 0

Now, we need to iterate for each value in array the M and fill it up. Also to store the minimum number of groups for each value, we will make a variable and initialize it with ∞

so that all other values are less than it in the starting.

for j in 1 to n
minimum = INF

Now for each j, we need to choose the minimum of Mn−di+1

, where di will change from d1 to dk and thus, i will change from 1 to k. Also, if the value of di

is greater than j (value to be made), then of course, we can't use that coin.

for j in 1 to n
minimum = INF
for i in 1 to k
if j >= d[i]
minimum = min(minimum, 1 + M[j-d[i]])

for i in 1 to n → We are iterating to change the value of di

from d1 to dk

.

if j >= d[i] → If the value to be made (j) is greater than the value of the current coin (d[i]), only then we can use this coin.

minimum = min(minimum, 1 + M[j-d[i]]) → If the current value of M[j-d[i]] (or Mj−di

) is less than the current minimum, then we are changing the value of the 'minimum'.

Now we just need to change the value of the array M to the calculated minimum and return it.

for j in 1 to n
minimum = INF
for i in 1 to k
...
M[j] = minimum
return M[n]

pseudo-code:

MONEY-LAUNDER(d, n, k)
M[n+1]
M[0] = 0

for j in 1 to n
minimum = INF

for i in 1 to k
if j >= d[i]
minimum = min(minimum, 1+M[j-d[i]])

M[j] = minimum
return M[n]
The time for each sub-problem is O(1), so the total run time of the code will be O(nD) n->no.of denomination D->amount of money

I hope this answer is helpful to you, please upvote my answer. I'm in need of it.. Thank you..