This question illustrates the Change problem and the use of Dynamic programming.
The running complexity of RecursiveChange(M,c,d) is in $O(d^M)$ The running complexity of DPChange(M,c,d) is in $O(Md)$.
For the dynamic programming algorithm the minimum number of coins needed is computed for every value up to the value which is asked for. The results are stored in a list and used for the computation of higher values. Therefore first you initalize the list with the needed coins with the single element 0 as for the value 0, no coins are needed to make change. Then for every value up to the value which has been asked for you append a new element to the list which is set to infinity. Then you you go through all you denominations and check if the denomination is smaller than your value. If this is true you can test if the number of needed coins for the given denomination would be smaller than the already tested denominations. If so you can update the number of needed coins for the values which is computed at this step.
For the value 11 and the denominations 1,3,4 the algorithm does the following with the list of needed coins.
[0]
[0, inf]
[0, 1]
[0, 1, inf]
[0, 1, 2]
[0, 1, 2, inf]
[0, 1, 2, 3]
[0, 1, 2, 1]
[0, 1, 2, 1, inf]
[0, 1, 2, 1, 2]
[0, 1, 2, 1, 1]
[0, 1, 2, 1, 1, inf]
[0, 1, 2, 1, 1, 2]
[0, 1, 2, 1, 1, 2, inf]
[0, 1, 2, 1, 1, 2, 3]
[0, 1, 2, 1, 1, 2, 2]
[0, 1, 2, 1, 1, 2, 2, inf]
[0, 1, 2, 1, 1, 2, 2, 3]
[0, 1, 2, 1, 1, 2, 2, 2]
[0, 1, 2, 1, 1, 2, 2, 2, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 3]
[0, 1, 2, 1, 1, 2, 2, 2, 2]
[0, 1, 2, 1, 1, 2, 2, 2, 2, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 4]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3, 4]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3, 3]
In [1]:
def DPChange(M,c,d):
import math
best_num_coins = [0]
for m in range(1,M+1):
best_num_coins.append(math.inf)
for i in range(0,d):
if m >= c[i]:
if best_num_coins[m-c[i]] +1 < best_num_coins[m]:
best_num_coins[m] = best_num_coins[m-c[i]] + 1
return best_num_coins[M]
In [2]:
DPChange(11,[1,3,4], 3)
Out[2]:
Longest Path Problem : The goal of this problem is to use the directed graph as in Fig. 1 and to find the longest path from E1 to D6.
In [112]:
import numpy as np
n = -np.inf
# E1 M1 G1 D1 D2 M2 G2 D3 M3 G3 D4 E2 E3 D5 D6
adjacency = np.matrix([[n, 0, 0, 0, n, n, n, n, n, n, n, n, n, n, n], #E
[n, n, 0, 20, n, 20, 20, n, n, n, n, n, n, n, n],#M1
[n, n, n, n, n, 15, 15, n, n, n, n, n, n, n, n], #G1
[n, n, n, n, 10, n, 10, n, n, n, n, n, n, n, n], #D1
[n, n, n, n, n, n, n, 15, n, n, n, n, n, n, n], #D2
[n, n, n, n, n, n, n, n, 20, 20, 20, n, n, n, n],#M2
[n, n, n, n, n, n, n, n, n, 20, n, n, n, n, n], #G2
[n, n, n, n, n, n, n, n, 20, n, 20, n, n, n, n], #D3
[n, n, n, n, n, n, n, n, n, n, n, 15, n, n, n], #M3
[n, n, n, n, n, n, n, n, n, n, n, 5, n, n, n], #G3
[n, n, n, n, n, n, n, n, n, n, n, 10, n, n, n], #D4
[n, n, n, n, n, n, n, n, n, n, n, n, 45, n, n], #E2
[n, n, n, n, n, n, n, n, n, n, n, n, n, 10, n], #E3
[n, n, n, n, n, n, n, n, n, n, n, n, n, n, 5], #D5
[n, n, n, n, n, n, n, n, n, n, n, n, n, n, n]]) #D6
def MTP(adj):
'''
This function returns the length of thlongest path of a
directed acyclic graph. Therefore it can solve the Manhattan
Tourist Problem.
This function works only on adjacency matrices
in which the nodes are ordered topologically.
'''
import numpy as np
score = {0:0}
for node in range(1,adj.shape[0]):
possibilities = []
for in_edge in range(adj.shape[1]):
if adj[in_edge,node] >= 0:
possibilities.append(adj[in_edge,node] + score[in_edge])
score[node] = max(possibilities)
return score[adj.shape[1]-1]
MTP(adjacency)
Out[112]:
The longest path is E1->M1->D1->D2->D3->M3->E2->E3->D5->D6