Daniel was dreaming of traveling to other mystic countries. In his dream, he was
ID: 3679493 • Letter: D
Question
Daniel was dreaming of traveling to other mystic countries. In his dream, he was in a nice city and taking the sightseeing tours. The currency which is called Fantasy Dollar(FD) at this strange country was different from $. He took the sightseeing tour which costs 9FD.
1) He used greedy algorithm to give the currency change. (Hint: The new fantasy Dollar currency denominations are is 1 FD, 4 FD, 6 FD ). What is the least number of coins he may use?
2-)If we solve the coin change problem with Dynamic Programming Approach, do we still find the same answer? What is the difference? Show your work.
Introduction to Algoirthms Study Question
Explanation / Answer
GREEDY ALGORITHM:
S {}; // set that will hold the solution set.
Sum 0 sum of item in solution set
WHILE sum not = n
x = largest item in set C such that sum + x n
IF no such item THEN
RETURN "No Solution"
S S {value of x}
sum sum + x
RETURN S
Now for the given problem the largest value of the coin is 6, so 6 will be selected first. Then the solution set will have 6 in it. S={6}
The next largest value given is 4. If add 4 to 6 it will be greater than 9. So this case cannot be considered.
Then the next largest value in the set is 1. If 1 is added to 6, it is less than 9. So 1 and 6 will be in the solution set S={6,1} . Again if we repeat the process we observe that 1 will satisfy the condition , so the solution set will have 6 and two 1’s in it (S={6,1,1} ) as the sum is not equal to 9 still, the while loop will execute once again and this time another 1 is added to the solution set then S={6,1,1,1}. So greedy method uses one 6FD and three 1FD’s.
DYNAMIC PROGRAMMING:
If P is the amount to be changed then we define C(p) as
C[p] =0 if p = 0
mini:dip{1 + C[pdi]} if p > 0
Change(d,k,n)
1 C[0] 0
2 for p 1 to n
3 min
4 for i 1 to k
5 if d[i] p then
6 if 1 + C[pd[i]] < min then
7 min 1 + C[pd[i]]
8 coin i
9 C[p] min
10 S[p] coin
11 return C and S
When the above procedure terminates, for all 0 p n, C[p] will contain the correct minimum number of coins needed to make change for p FD’s, and S[p] will contain (the index of) the rst coin in an optimal solution to making change for p FD’s
In our problem p=9, di ={1, 4, 6}
P 0 1 2 3 4 5 6 7 8 9
C(p) 0 1 2 3 1 2 1 2 2 3
S[p] 0 1 1 1 2 2 3 3 2 1&2
C(0)= 0 as p=0
C[1] = min(1+C[1-1])=min(1+C[0])= min(1+0)=1(as d1 =1and p=1)
C[2]= min(1+C[2-1])=min(1+C[1])= min(1+1)=2(as d1 =1 and p=2)
C[3]= min(1+C[3-1])=min(1+C[2])= min(1+2)=3(as d1 =1 and p=3)
C[4]= min(1+C[4-1], 1+C[4-4])= min(1+C[3],1+C[0])=min(1+3,1+0)
=min(4,1)=1(as now d has two values 1 and 4 and p=4)
C[5]=min(1+C[5-1], 1+C[5-4])=min(2,2)=2
C[6]= min(1+C[6-1],1+C[6-4],1+C[6-6])
= min(1+C[5],1+C[2],1+C[0])= min(1+2,1+2,1+0)=min(3,3,1)=1
( as d takes all the three values at 6)
C[7]= min(1+C[7-1],1+C[7-4],1+C[7-6])=min(2,4,2)=2
C[8]= min(1+C[8-1],1+C[8-4],1+C[8-6])=min(3,2,3)=2
C[9]= min(1+C[9-1],1+C[9-4],1+C[9-6])=min(3,3,4)=3
Therefore we need three coins for optimal solution.
The min values in C[9] are encountered for d1 and d2 so 1 and 4 will be used to get the required value that is 9. So according to dynamic programming two 4FD’s and one 1FD are used.
Both the algorithms give different solutions.