Daniel was dreaming of traveling to other mystic countries. In his dream, he was

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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.