Greedy Algorithms
• Knapsack
• Scheduling
• Huffman Code
• Coin Change
1
Optimization Problems
• Optimization problem: a problem of finding the best solution
from all feasible solutions.
• Two common techniques:
– Greedy Algorithms
– Dynamic Programming (global)
Elements of Greedy Strategy
• Greedy-choice property: A global optimal solution can
be arrived at by making locally optimal (greedy) choices
• Optimal substructure: an optimal solution to the
problem contains within it optimal solutions to sub-
problems
Greedy Algorithms
A greedy algorithm works in phases. At each phase:
– You take the best you can get right now,
without regard for future consequences
– You hope that by choosing a local optimum at
each step, you will end up at a global optimum
Greedy algorithms typically consist of
– A set of candidate solutions
– Function that checks if the candidates are feasible
– Selection function indicating at a given time which
is the most promising candidate not yet used
– Objective function giving the value of a solution;
this is the function we are trying to optimize
4
Analysis
• The selection function is usually based on the objective
function; they may be identical. But, often there are
several plausible ones.
• At every step, the procedure chooses the best
candidate, without worrying about the future. It never
changes its mind: once a candidate is included in the
solution, it is there for good; once a candidate is
excluded, it’s never considered again.
• Greedy algorithms do NOT always yield optimal
solutions, but for many problems they do.
Greedy vs DP
• Greedy and Dynamic Programming are methods for solving
optimization problems.
• Greedy algorithms are usually more efficient than DP
solutions.
• However, often you need to use dynamic programming since
the optimal solution cannot be guaranteed by a greedy
algorithm.
• DP provides efficient solutions for some problems for which a
brute force approach would be very slow.
• To use Dynamic Programming we need only show that the
principle of optimality applies to the problem.
Examples of Greedy Algorithms
• Knapsack
• Data compression
– Huffman coding
• Scheduling
– Activity Selection
– Task Scheduling
– Minimizing time in system
– Deadline scheduling
• Coin Change
• Graph Algorithms
– Breath First Search (shortest path 4 un-weighted
graph)
– Dijkstra’s (shortest path) Algorithm
– Minimum Spanning Trees
The 0/1 Knapsack problem
• Given a knapsack with weight W > 0.
• A set S of n items with weights wi >0 and
values vi> 0 for i = 1,…,n.
• S = { (item1, w1, v1 ), (item2, w2, v2 ) ,
. . . , ( itemn, wn, vn ) }
• Find a subset of the items which does not exceed the weight
W of the knapsack and maximizes the value.
Greedy 1: Selection criteria: Maximum valued item.
Counter Example:
S = { ( item1 , 5, $70 ), (item2 ,10, $90 ), ( item3, 25, $140 ) }
$140
10 lb
W=
25lb
$90 $140 $70
5 lb
25 lb
$70 25 lb
$90
10 lb 10 lb
5 lb 10 lb
item1 item2 item3 Knapsack Greedy Optimal
=$140 =$160
Solution Solution
Greedy 2: Selection criteria: Minimum weight item
Counter Example:
S = { ( item1 , 5, $150 ), (item2 ,10, $60 ), ( item3, 20, $140 ) }
5 lb
$140
W=
30lb $140
20 lb
$60 10 lb $60
20 lb
$150 10 lb
$150
5 lb 5 lb $150 5 lb
item1 item2 item3 Knapsack Greedy Optimal =$290
=$210
Solution Solution
Greedy 3: Selection criteria: Maximum weight item
Counter Example:
S = { ( item1 , 5, $150 ), (item2 ,10, $60 ), ( item3, 20, $140 ) }
5 lb
10 lb
$60
$140
W=
30lb $140
20 lb
$60
20 lb
$150 10 lb 20 lb
$140 $150
5 lb 5 lb
item1 item2 item3 Knapsack Greedy Optimal
=$200 =$290
Solution Solution
Greedy 4: Selection criteria: Maximum value per unit item
Counter Example
S = { ( item1 , 5, $50 ), ( item2, 20, $140 ) (item3 ,10, $60 ), }
5 lb
V/W: $7
$140
W=
30lb 20 lb $140
$140
V/W 2: $6
20 lb
V/W 1: $10 $60
20 lb
$50 10 lb $60
10 lb $50
5 lb 5 lb
item1 item2 item3 Knapsack Greedy Optimal =$200
=$190
Solution Solution
14
15
Fractional Knapsack
Let k be the index of the last item included in the knapsack. We may be
able to include the whole or only a fraction of item k
k 1
Without item k totweight = w
i 1
i
𝑘−1
FWK = 𝑖=1 𝑣𝑖 + min{(W - totweight),wk } X (vk / wk )
min{(W - totweight),wk }, means that we either take the whole of item
k when the knapsack can include the item without violating the
constraint, or we fill the knapsack by a fraction of item
A Greedy Algorithm for Fractional Knapsack
In this problem a fraction of any item may be chosen
The greedy algorithm uses the maximum benefit per unit
selection criteria
1. Calculate ratio vi / wi for 1≤i≤n (n)
2. Sort items in decreasing vi / wi. (nlgn)
3. Add items to knapsack (starting at the first) until there
are no more items, or until the capacity W is exceeded.
If knapsack is not yet full, fill knapsack with a fraction
of next unselected item. (n)
Running time: (nlgn)
The Fractional Knapsack Algorithm
Algorithm FKnapsack(S, W)
• Greedy choice: Keep
taking item with Input: set S of items w/ value vi
highest value to weight and weight wi; max. weight W
ratio Output: amount xi of each item i
– Use a heap-based to maximize total value with
priority queue to store weight at most W
the items, then the time
complexity is O(n log n). for each item i in S
xi 0
ri vi / wi {ratio}
w0 {current total weight}
while w < W
remove item i with highest ri
xi min{wi , W w}
w w + min{wi , W w} 18
Example of applying the optimal greedy algorithm for Fractional
Knapsack Problem
S = { ( item1 , 5, $50 ), ( item2, 20, $140 ) (item3 ,10, $60 ), }
5 lb 5/10 * $60 = $30
V/W: $7
$140
30lb Optimal benefit
Max $140 $220
V/W 2: $6 Solution: items
20 lb
1and 2
V/W 1: $10 $60
20 lb and 1/2 of item 3
$50 10 lb
$50
5 lb 5 lb
item1 item2 item3 Knapsack Greedy = Optimal
Solution Solution
Fractional Knapsack
• Goal: Choose items with maximum total value but with weight
at most W. You can now use fractions of items
“knapsack”
Items:
A B C D E
Weight: 4 ml 8 ml 2 ml 6 ml 1 ml
Value: $24 $24 $30 $30 $7 10 ml
What is the maximum value?
a) 84
b) 76
c) 54
d) 67
e) None of the above 20
Fractional Knapsack
• Goal: Choose items with maximum total value but with weight
at most W.
“knapsack”
Solution:
•2 ml of C - $30
Items:
A B C D E • 1 ml of E - $7
• 4 ml of A -$24
Weight: 4 ml 8 ml 2 ml 6 ml 1 ml •3 ml of D - $15
Value: $24 $24 $30 $30 $7 10 ml •____________
Ratio: 6 3 15 5 7 10 ---- $ 76
($ per ml)
21
Fractional Knapsack has greedy choice property
That is, if vi/wi is the maximum ratio, then there exists an optimal
solution that contains item xi up to the extent of min{wi, W}.
Proof (by contradiction): Assume that there does not exist an
optimal solution that contains xi. Let O = {xj , .., xk } be an optimal
solution that does not contain xi. Let xt be the item with maximum
weight wt in O.
1) If wt wi, then replace wi amount of xt by wi amount of xi. This
will either increase the value of the solution if vi/wi > vt/wt or be
an alternative maximum solution if vi/wi = vt/wt
2) If wt < wi, then
a) Let S be a subset of items in O whose is total weight is
greater than wi. Replacing wi of this total weight by wi of xi
will improve the value of the solution.
Fractional Knapsack has greedy choice property
b) If no such set S exists then the sum of the weights of all
items in O = W ≤ wi. Replace all the items in O by W units of
xi and the solution will improve (or leading to an alternative
solution containing xi ).
Therefore we have shown that adding item xi to O will improve the
solution or lead to an alternative maximum solution.
24
25
Activity Scheduling: Greedy Algorithms
Greedy. Consider activities in some natural order.
Take each activity provided it's compatible with the ones already
taken.
– [Earliest start time] Consider activities in ascending order of sj.
– [Earliest finish time] Consider activities in ascending order of fj.
– [Shortest interval] Consider activities in ascending order of
fj - sj.
– [Fewest conflicts] For each activity j, count the number of
conflicting activities cj. Schedule in ascending order of cj.
26
Greedy Algorithms are not always Optimal
Counterexample for earliest start time
Counterexample for shortest interval
Counterexample for fewest conflicts
27
Earliest Finish Greedy Strategy
• Select the activity with the earliest finish
• Eliminate the activities that could not be
scheduled
• Repeat!
• Greedy in the sense that it leaves as much
opportunity as possible for the remaining
activities to be scheduled
• The greedy choice is the one that maximizes
the amount of unscheduled time remaining
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Assuming activities are sorted by
finish time
a) Mergesort 3 faster
b) MergeSort faster
c) same
37
Given the activities below what is the maximum number
of activities that can be scheduled?
Act # 1 2 3 4 5 6
Start 1 2 2 4 5 7
Finish 3 6 4 6 7 10
a) 1
b) 2
c) 3
d) 4
e) None of the above
38
Last-to-Start
Act # 1 2 3 4 5 6
Start 1 2 2 4 5 7
Finish 3 6 4 6 7 10
39
First-to-Finish
Act # 1 2 3 4 5 6
Start 1 2 2 4 5 7
Finish 3 6 4 6 7 10
40
41
Elements of Greedy Strategy
• An greedy algorithm makes a sequence of choices,
each of the choices that seems best at the moment is
chosen
– NOT always produce an optimal solution
• Two ingredients that are exhibited by most problems
that lend themselves to a greedy strategy
– Optimal substructure
– Greedy-choice property
Optimal Substructures
Step 1: Characterize optimality
Without loss of generality, we will assume that the a's are sorted in
non-decreasing order of finishing times, i.e. f1 ≤ f2 ≤ ... ≤ fn.
Define the set Sij
Sij = {ak ∈ S : fi ≤ sk < fk ≤ sj} as the subset of activities that can occur
between the completion of ai (fi) and the start of aj (sj).
Note that Sij = ∅ for i ≥ j since otherwise fi ≤ sj < fj ⇒ fi < fj which is a
contradiction for i ≥ j by the assumption that the activities are in sorted order.
43
Optimal Substructures
Define the set Sij
Sij = {ak ∈ S : fi ≤ sk < fk ≤ sj} as the subset of activities that can
occur between the completion of ai (fi) and the start of aj (sj).
Let Aij be the maximal set of activities for Sij. Using a "cut-and-
paste" argument, if Aij contains activity ak then we can write
Aij = Aik ∪ {ak} ∪ Akj
where Aik and Akj must also be optimal (otherwise if we could find
subsets with more activities that were still compatible
with ak then it would contradict the assumption that Aij was
optimal).
44
Step 2: Define the recursive solution (top-down)
Let c[i,j] = |Aij|, then
i.e. compute c[i,j] for each k = i+1, ..., j-1 and select the
max.
This would take exponential time!
45
Step 2: Define the recursive solution (top-down)
Let c[i,j] = |Aij|, then
i.e. compute c[i,j] for each k = i+1, ..., j-1 and select the
max.
Step 3: Compute the maximal set size (bottom-up)
Construct an nxn table which can be done in polynomial
time since clearly for each c[i,j] we will examine no
more than n subproblems giving an upper bound on the
worst case of O(n3).
46
BUT WE DON'T NEED TO DO ALL THAT WORK!
• Instead at each step we could simply select
(greedily) the activity that finishes first and is
compatible with the previous activities. Intuitively
this choice leaves the most time for other future
activities.
Greedy Algorithm Solution
• To use the greedy approach, we must prove that
the greedy choice produces an optimal solution
(although not necessarily the only solution).
47
Greedy Choice Property
To use the greedy approach, we must prove that the greedy
choice produces an optimal solution (although not necessarily
the only solution).
Let Sk = {ai ∈ S k : si ≥ fk} be the set of activities that start after
activity ak finishes
Consider any non-empty subproblem Sk with activity am having
the earliest finishing time, Then am included in some maximum-
size subset of mutually compatible activities of Sk .
48
Greedy Choice Property
Note: If we make the greedy choice of a1 then S1 remains the
only subproblem to solve. That is S01 = .
fm = min{fk : ak ∈ Sij}
then the following two conditions must hold
[Link] is used in an optimal subset of Sij
[Link] = ∅ leaving Smj as the only subproblem
meaning that the greedy solution produces an optimal solution.
49
Consider any non-empty subproblem Sk with activity am having
the earliest finishing time, Then am included in some
maximum-size subset of mutually compatible activities of Sk .
Let Ak be an optimal solution for Sk and aj be the activity in Ak
with the earliest finish time.
• If aj = am then the condition holds.
• If aj ≠ am then construct Ak' = Ak - {aj} ∪ {am}.
Since fm ≤ fj ⇒ Ak' is still optimal.
The activities in are disjoint since the activites in are disjoint and
fm ≤ fj . Since |Ak | = | Ak' |, we conclude that Ak is a maximum-size
subset of mutually compatible activates for Sk and include am.
50
51
Machine Scheduling with start times
• Given: a set T of n tasks, each having:
– A start time, si
– A finish time, fi (where si < fi)
• Goal: Perform all the tasks using a minimum
number of “machines.”
Machine 3
Machine 2
Machine 1
1 2 3 4 5 6 7 8 9
52
Example
• Given: a set T of n=7 tasks, each having:
– A start time, si
– A finish time, fi (where si < fi)
– [1,4], [1,3], [2,5], [3,7], [4,7], [6,9], [7,8] (ordered by start)
• Goal: Perform all tasks on min. number of machines
Machine 3
Machine 2
Machine 1
1 2 3 4 5 6 7 8 9
53
54
Machine Scheduling Algorithm
• Greedy choice: consider tasks by their
start time and use as few machines as
possible with this order. Algorithm TaskSchedule(T)
– Run time: O(n log n) depending on Input: set T of tasks w/ start time si
data structure used. and finish time fi
• Correctness: Suppose there is a better Output: non-conflicting schedule
schedule. with minimum number of machines
– We can use k-1 machines
m0 {no. of machines}
– The algorithm uses k
– Let i be first task scheduled on while T is not empty
machine k remove task i w/ smallest si
– Task i must conflict with k-1 other if there’s a machine j for i then
tasks
– K mutually conflict tasks schedule i on machine j
– But that means there is no non- else
conflicting schedule using k-1 mm+1
machines
schedule i on machine m
55
To get O(log(n)) for each iteration, keep the machines in a heap using as key
the latest finishing time assigned to that machine. This tells you when that
machine will be free. When you select the next task i with start time si, and
finishing time fi check the min element of the machine heap say machine j
with key fj indicate it is free at time fj
• If machine j is free at time si (si >= fj) then it is free forever starting at si.
We can now
1. Remove the machine j from the heap (removeMin), O(logn).
2. Assign the current job to the removed machine j, Θ(1).
3. Now machine j is free at fi and we re-insert it into the heap, O(logn).
• If machine j is not free at si, then no machine is free at si since this was the
minimum free time, so
1. Increase m generating a new machine, Θ(1).
2. Assign i to the new machine m, Θ(1).
3. Insert machine m (which has key fi) into the heap, O(logn).
Note there are n iterations if n jobs that need to be scheduled on machines
so O(nlgn) overall running time.
56
Job Scheduling Problem
• There is no specified start times only durations.
• You have to run nine jobs, with running times of 3, 5, 6, 10, 11,
14, 15, 18, and 20 minutes
• You have three processors on which you can run these jobs
• You decide to do the longest-running jobs first, on whatever
processor is available
P1 20 10 3
P2 18 11 6
P3 15 14 5
Time to completion: 18 + 11 + 6 = 35 minutes
This solution isn’t bad, but we might be able to do better
57
Another approach
• What would be the result if you ran the shortest job first?
• Again, the running times are 3, 5, 6, 10, 11, 14, 15, 18, and 20
minutes
P1 3 10 15
P2 5 11 18
P3 6 14 20
That wasn’t such a good idea; time to completion is now
6 + 14 + 20 = 40 minutes
Note, however, that the greedy algorithm itself is fast
– All we had to do at each stage was pick the minimum or maximum
58
An optimum solution
P1 20 14
P2 18 11 5
P3 15 10 6 3
• This solution is clearly optimal (why?)
• Clearly, there are other optimal solutions (why?)
• How do we find such a solution?
– One way: Try all possible assignments of jobs to processors
– Unfortunately, this approach can take exponential time
59
Announcements
• Quiz 4 – Due Sunday
• HW 4 – Due next Tuesday
• Finish Greedy Algorithms
• Questions on HW 4
• Weeks 6 & 7 Graph Algorithms
60
61
Huffman Codes
Text Compression (Zip)
– On a computer: changing the representation of a
file so that it takes less space to store or/and less
time to transmit.
– Original file can be reconstructed exactly from the
compressed representation
- Very effective technique for compressing data,
saving 20% - 90%.
Huffman Coding
• As an example, lets take the string:
“ABRACADABRA”
• We first to a frequency count of the characters:
• A:5, B:2, C:1, D:1, R:2
• Next we use a Greedy algorithm to build up a
Huffman Tree
– We start with nodes for each character
A,5 B,2 R,2 D,1 C,1
Huffman Coding
• We then pick the nodes with the smallest
frequency and combine them together to
form a new node
– The selection of these nodes is the Greedy part
• The two selected nodes are removed from the
set, but replace by the combined node
• This continues until we have only 1 node left
in the set
Huffman Coding
A,5 B,2 R,2 D,1 C,1
Huffman Coding
A,5 B,2 R,2 2
D,1 C,1
Huffman Coding
A,5 4 B,2
R,2 2
D,1 C,1
Huffman Coding
A,5 4 B,2
R,2 2
D,1 C,1
Huffman Coding
A,5 6
B,2 4
R,2 2
D,1 C,1
Huffman Coding
0 11
1
A,5 6
0 1
B,2 4
0 1
A=0
R,2 2
B = 10 1
R = 110 0
D = 1110 D,1 C,1
C = 1111
Code word
01011001111011100101100 = 23 bits << 33 bits
A=0
B = 10
R = 110
D = 1110
C = 1111
However…
• There are some concerns…
• Suppose we have
– A-> 01
– B-> 0101
• If we have 010101, is this AB? BA? Or AAA?
• Therefore: prefix codes, no codeword is a prefix of
another codeword, is necessary
Prefix Codes
• Any prefix code can be represented by a full binary
tree
• Each leaf stores a symbol.
• Each node has two children – left branch means 0,
right means 1.
• codeword = path from the root to the leaf
interpreting suitably the left and right branches
How do we find the optimal coding tree?
• It is clear that the two symbols with the smallest
frequencies must be at the bottom of the optimal
tree, as children of the lowest internal node
• This is a good sign that we have to use a bottom-up
manner to build the optimal code!
• Huffman’s idea is based on a greedy approach, using
the previous notices.
Huffman codes
• Idea: build tree bottom-up and make greedy
choice (what is it?)
– joining two symbols commits to a bit to
distinguish them; which should we choose?
1. build heap H with frequencies as keys
2. for i = 1 to n-1
3. allocate new node z
4. [Link] = x = EXTRACT-MIN(H)
5. [Link] = y = EXTRACT-MIN(H)
6. z. freq = [Link] + [Link]; INSERT(H, z)
7. return EXTRACT-MIN(H)
Running time
• Build-Min-Heap O(n)
• Each Extract-Min O(lgn) for a total of O(nlgn)
• Overall O(nlgn)
Given the frequency table below:
T A M P O
.29 .36 .10 .05 .20
What is the code for A ?
a) 0
b) 1
c) 01
d) 10
e) None of the above
77
Given the frequency table below:
T A M P O
.29 .36 .10 .05 .20
What is the code for A ?
a) 0
b) 1
c) 01
d) 10
e) None of the above
78
79
80
81
Another Example
Example:
• can represent prefix-free encoding scheme by
binary tree T:
• Problem: given
frequencies, construct
optimal tree (prefix-free
encoding scheme)
Huffman example from CLRS
Huffman example from CLRS
Decoding
• Suppose we have the
Following code:
1010111
• What is the decode
result?
Decoding
• Suppose we have the
Following code:
1010111
• What is the decode
result? b
Decoding
• Suppose we have the
Following code:
1010111
• What is the decode
result? ba
Decoding
• Suppose we have the
Following code:
1010111
• What is the decode
result? bad
89
Coin Change
• Coin changing problem (informal):
– Given certain amount of change: A
– The denominations of coins are: 25, 10, 5, 1
– How to use the fewest coins to make this change?
• A = 25q + 10d + 5n + p, what are the q, d, n, and p,
minimizing (q+d+n+p)
• Can you design an algorithm to solve this problem?
90
Coin changing problem
• Greedy choice
– Choose as many of the largest coins available.
• Optimal substructure
– After the greedy choice, assuming the greedy
choice is correct, can we get the optimal solution
from a subproblem.
– Given A = 63 cents
• Assuming we have chosen 2*25 = 50
• Is two quarters + optimal coin(63-50) the optimal
solution of 63 cents?
Coin Change
• Step 1: A = 63
92
Coin Change
• Step 1: A = 63, q = 2
93
Coin Change
• Step 1: A = 63, q = 2
• Step 2: (63-50) = 13
94
Coin Change
• Step 1: A = 63, q = 2
• Step 2: (63-50) = 13, d = 1
95
Coin Change
• Step 1: A = 63, q = 2
• Step 2: (63-50) = 13, d = 1
• Step 3: (13-10) = 3
96
Coin Change
• Step 1: A = 63, q = 2
• Step 2: (63-50) = 13, d = 1
• Step 3: (13-10) = 3
97
Coin Change
• Step 1: A = 63, q = 2
• Step 2: (63-50) = 13, d = 1
• Step 3: (13-10) = 3, p = 3
98
Coin Change
• Step 1: A = 63, q = 2
• Step 2: (63-50) = 13, d = 1
• Step 3: (13-10) = 3, p = 3
• Number of coins = 6
99
Coin Change
• Step 1: A = 63, q = 2
• Step 2: (63-50) = 13, d = 1
• Step 3: (13-10) = 3, p = 3
• Number of coins = 6
• For coin denominations of 25, 10, 5, 1
– The greedy choice property is not violated
100
101
102
A failure of the Greedy Algorithm
• Suppose in a fictional monetary system, we
have 1 , 3, 6 , and 10 cent coins
• The greedy algorithm results in a solution,
but not in an optimal solution
103
Coin Change Fail
• Step 1: A = 12
10
3 6
1
104
Coin Change Fail
• Step 1: A = 12 10
• Step2: (12-10) = 2
10
3 6
1
105
Coin Change Fail
• Step 1: A = 12 10
• Step2: (12-10) = 2 1 1
This is three coins
The optimal solution is two coins 10
6 6
3 6
1
106
Making Change DP
Given coins of denominations (value) 1 = v1 < v2< … < vn, we wish to make change for
an amount A using as few coins as possible. Assume that vi’s and A are
integers. Since v1= 1 there will always be a solution.
Formally, an algorithm for this problem should take as input:
An array V where V[i] is the value of the coin of the ith denomination.
A value A which is the amount of change we are asked to make
The algorithm should return an array C where C[i] is the number of coins of value
V[i] to return as change and m the minimum number of coins it took.
The objective is to minimize the number of coins returned or:
𝑛
m = min 𝐶𝑖
𝑖=1
𝑛
Subject to : 𝑖=1 𝑉 𝑖 ∙𝐶 𝑖 =𝐴
107
Let coins[k] be the number of coins used to make change
for k cents. V[i] is the value (denomination) of the ith coin.
sol[k] is the index of last denomination V[sol[k]] used to
obtain change for k cents
Formulas
coins[i] = inf if i < 0
coins[0] = 0
coins[1]= 1
coins[j] = 𝐦𝐢𝐧 𝟏 + 𝒄𝒐𝒊𝒏𝒔[𝒋 − 𝒗𝒊 ] , sol[j] = i
𝟏≤𝒊≤𝒏
Sample pseudocode
minCoins(A, V[], n)
coins[0]=0; coins[1] = 1
for j = 2 to A do {
min = inf
for i = 1 to n do {
if ( j >= V[i] )
if ( (coins[j-V[i]] + 1) < min )
{
min = coins[j-V[i]] + 1
index = i
}
}
coins[j] = min
sol[j] = index
}
return coins[A], sol[A]
To reconstruct the series of coins used to obtain change for A with minimum
number of coins. Call MakeChange(sol, V, A).
MakeChange(sol[], V[], m)
C[] = 0;
while m > 0 {
Print V[sol[m]]
C[sol[m]] = C[sol[m]] + 1
m = m – V[sol[m]]
}
• V[i] is the value of the ith coin.
• Sol[j] is the index of the last coin to make change for an amount
of j
• C[i] is the number of times the ith coin is used in the solution.
Theoretical running time
• The running time of MakeChange is O(A)
• The running time of minCoins is (nA) since
the outer loop is j = 2 ..A and inner loop is i = 1
..n.
• Overall (nA)
Example
V = { 1, 3, 6, 10} V[1]=1, V[2]=3, V[3] = 6, V[4] = 10, A = 12
Coin[a] minimum # of coins to make amount a
Coin[0] = 0 no coins
Coin[1] = 1 sol[1]=1 use a 1 cent
Coin[2] = 2 sol[2]=1
Coin[1] + 1 = 2 use a 1 cent coin
Coin[3] = 1 sol[3] = 2
Coin[2] + 1 = 3 use the 1 cent coin and have 2 cents left over
Coin[0] + 1 = 1 use the 3 cent coin v[2]
Coin[4] = 2 sol[4] = 1
Coin[3] + 1 = 2 use a 1 cent
Coin[1] + 1 = 2 use a 3 cent
112
V = { 1, 3, 6, 10} V[1]=1, V[2]=3, V[3] = 6, V[4] = 10, A = 12
Coin[5] = 3 sol[5] = 1
Coin[4] + 1 = 3 use a 1 cent
Coin[2] + 1 = 3 use the 3 cent
Coin[6] = 1 sol[6] = 3
Coin[5] + 1 = 4 use a 1 cent ( 1 , 1 3)
Coin[3] + 1 = 2 use a 3 cent ( 3 cent)
Coin[0] + 1 = 1 use the 6 cents
……
Coin[12] sol[12] = 3
Coin[11] + 1 = 3 last coin 1 cent
Coin[9] + 1 = 3 last coin 3 cent
Coin[6] + 1 = 2 last coin 6 cent
Coin[2] + 1 = 3 last coin 10 cent
113
To reconstruct the series of coins used to obtain change for A
with minimum number of coins. Call MakeChange(sol, V, A).
MakeChange(sol[], V[], m)
C[] = 0;
while m > 0 {
Print V[sol[m]]
C[sol[m]] = C[sol[m]] + 1
m = m – V[sol[m]]
}
sol[12] = 3, V[3] = 6, C[3] = 1
m= 12-6 = 6
sol[6] = 3, V[3] = 6, C[3] = 1+1 = 2
m = 6-6 = 0;