Question

(a)
You have a crisis of conscience and you have decided to donate the funds to charity. You want
to divide D dollars (in integer values) to different charities. You want to give at most L dollars to
one single charity. You are concerned that the FBI will come knocking at your door at any
moment, so you want to donate the larger amounts as soon as possible (and you want to
donate the lesser amounts later on). In other words, your first donation is larger than or equal
to your second donation, and so on. In pseudo-code, write a dynamic programing algorithm to
compute the number of ways you can divide the funds. Can you write a solution in O(DL)?
Explain your answer.

(b) Write a python procedure for (a) that takes an input D and L and returns the number of
ways of dividing the funds. Output your solution when D = 1000 and L = 15.

Answer 1

a.) We can donate at most 'L' dollars at once.

We can donate 1 to min(L, D) dollars at a time, where 'D' is the remaining amount of money that we have.

If we have donated 'K' dollars in current donation we must have to donated less that or equal to "K" dollars in next donation.

Keeping these points in mind, lets design algo.

Algorithm:-

• Lets call function name "TotalNumberOfWays(D, last)" that will return number of ways with "D" dollars, "last" dollars donated in previous donation.
• We can pick 1 to min(last, D) amount to donate in current donation, Initial value of will be "L". Lets say we have donated "K" amount of money in current donation than "TotalNumberOfWays(D, K)" will be call for next donation.
• We will store value computed in call "TotalNumberOfWays(D, last)" so that we do not need to compute this value again (Dynamic programming). Lets call it "DP[][]" array and DP[D][last] will store number of ways for function call "TotalNumberOfWays(D, last)".

Psuedocode:-

TotalNumberOfWays(D, last):

if D == 0:

return 1

else if DP[D][last] is already computed:

return DP[D][last]

ways = 0

for K = last to 1:

ways += TotalNumberOfWays(D, K)

DP[D][last] = ways

return DP[D][ways]

b.) Python3 code:-

DP = [[None for i in range(16)]for j in range(1001)]
def TotalNumberOfWays(D, last):
   if D == 0:
       return 1
   elif DP[D][last] is not None:
       return DP[D][last]
   ways = 0
   for k in range(min(D, last), 0, -1):
       ways += TotalNumberOfWays(D-k, k)
   DP[D][last] = ways
   return DP[D][last]

ways = TotalNumberOfWays(1000, 15)
print("Total number of ways of donations : ", ways)

Screenshot of output:-