Idea of Greedy Algorithms

Typically, it is used to solve the optimization problems.
It obtains an optimal solution to a problem by making a sequence of choices and it always makes the choice that looks best at the moment.
It does not always yield optimal solution.
It is simple and efficient algorithm.
It solves the problem in a top-down manner.

ALGORITHM Greedy(C)
BEGIN
	S={}
	while(C!={})do
	begin
		x=select(C)
		C=C-{x}
		if(feasible(S∪{x}))then
		begin
			S=S∪{x}
			if(solution(S))then return S
		end
	end
	return “no solution”
END.

Note that C=candidate set and S=solution set.
The greedy-choice property and optimal substructure are the two key ingredients.
1. Greedy-choice property
  - A globally optimal solution can be obtained by making a locally optimal choice.
2. Optimal substructure
  - An optimal solution to the subproblem yields an optimal solution to the original problem.

Coin Changing

We want to make change for an amount N using the least number of coins of the denominations $d_1>d_2>\dotso>d_m$ used in that locale.
For example, the widely used coin denominations in Thailand are $d_1=10$ baht, $d_2=5$ baht, $d_3=2$ baht, $d_4= 1$ baht.
Greedy rule
- Select the largest denomination available. → ก็คือถ้าเป็นโปรแกรมก็เหมือนไล่จาก Index มากสุด

Example 1

Example: How would you give change 22 baht with coins of the given denomination?
- Step1: we need to make change for N=22
  C={10,5,2,1}
  S={10 * 2}=20
- Step2: we need to make change for N=2
  C={5,2,1}
  S={10 * 2+2 * 1}=22
Thus, we use 3 coins to make change for N=22.

Example 2

• Example: How would you give change 12 with coins of the given

denomination? d1=25, d2=10, d3=6, d4=5, and d5=1,.

Step1: we need to make change for N=12

C={25,10,6,5,1}

S={10 * 1}

Step2: we need to make change for N=2

C={6,5,1}

S={10 * 1+1 * 2}

Thus, we use 3 coins to make change for N=12, but it is not optimal

solution.

• The optimal solution to make change for N=12 is 2 coins (6 * 2).

Make

Kruskal’s Algorithm

• The minimum spanning tree is the problem of finding a minimum

spanning tree for a given weighted connected graph.

• Two classic algorithms for the minimum spanning tree problem:

Kruskal’s algorithm and Prim’s algorithm.

• A spanning tree of a connected graph is its connected acyclic subgraph

(i.e., a tree) that contains all the vertices of the graph.

• A minimum spanning tree of a weighted connected graph is its spanning

tree of the smallest weight, where the weight of a tree is defined as the

sum of the weights on all its edge.

• Greedy rule

Add an edge of minimum weight that does not make a cycle.

• The algorithm begin by sorting the graph’s edges in non

decreasing order of their weights.

• Then, starting with the empty subgraph, it scans this sorted list

adding the next edge on the list to the current subgraph if such an

inclusion does not create a cycle and simply skipping the edge

otherwise.

12 Graphs

Prim’s Algorithm

The Continuous-Knapsack Problem

05 Greedy Algorithms