Suppose the coinage includes the values given in Section 6.1, but you have run o
ID: 3679753 • Letter: S
Question
Suppose the coinage includes the values given in Section 6.1, but you have run out of nickels. Show that using the greedy algorithm with the remaining values does not necessarily produce an optimal solution. Section 6.1 function {make-change} (n): set of coins {Makes change for n units using the least possible number of coins. The constant C specifies the coinage} const C = {100, 25, 10, 5, 1} S leftarrow empty set{S is a set that will hold the solution} s leftarrow 0 {s is the sum of the items in S} while s not equal to n do x leftarrow the largest item in C such that s + xExplanation / Answer
Greedy Algorithm works by making the decision that seems most promising at any moment; it never reconsiders this decision, whatever situation may arise later.
total penny nickel dime quarter half
5 1 2 1 1
6 3 1 1 1
7 5 1 1
8 4 3 1
9 6 2 1
10 8 1 1
11 10 1
12 7 4 1
13 9 3 1
14 11 2 1
15 13 1 1
16 15 1
17 14 3
18 16 2
19 18 1
20 20
21 5 13 3
22 5 15 2
23 5 17 1
24 5 19
25 10 12 3
26 10 14 2
27 10 16 1
28 10 18
29 15 11 3
30 15 13 2
31 15 15 1
32 15 17
33 20 10 3
34 20 12 2
35 20 14 1
36 20 16
37 25 9 3
38 25 11 2
39 25 13 1
40 25 15
41 30 8 3
42 30 10 2
43 30 12 1
44 30 14
45 35 7 3
46 35 9 2
47 35 11 1
48 35 13
49 40 6 3
50 40 8 2
51 40 10 1
52 40 12
53 45 5 3
54 45 7 2
55 45 9 1
56 45 11
57 50 4 3
58 50 6 2
59 50 8 1
60 50 10
61 55 3 3
62 55 5 2
63 55 7 1
64 55 9
65 60 2 3
66 60 4 2
67 60 6 1
68 60 8
69 65 1 3
70 65 3 2
71 65 5 1
72 65 7
73 70 3
74 70 2 2
75 70 4 1
76 70 6
77 can't be done
78 75 1 2
79 75 3 1
80 75 5
81 can't be done
82 80 2
83 80 2 1
84 80 4
85 can't be done
86 can't be done
87 85 1 1
88 85 3
89 can't be done
90 can't be done
91 90 1
92 90 2
93-95 can't be done
96 95 1
97-99 can't be done
100 100
Change of N
C {100, 25, 10, 5, 1}
Sol {list of solutions};
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.