[go: up one dir, main page]
Scribd
Upload
140 views2 pages

Coin Changing Problem

The document discusses solving the coin changing problem using greedy and dynamic programming approaches. It provides examples of solving for change amounts using different sets of coins. The greedy approach is shown to fail for some cases, while dynamic programming can find a solution.

Uploaded by

Azka Aziz
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
140 views2 pages

Coin Changing Problem

The document discusses solving the coin changing problem using greedy and dynamic programming approaches. It provides examples of solving for change amounts using different sets of coins. The greedy approach is shown to fail for some cases, while dynamic programming can find a solution.

Uploaded by

Azka Aziz
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Coin changing problem:

Greedy approach:

N=20

Coin ={1,5,10}

20-10=10 1

10-10=0 2

(10+10 ) rs have two 2 coin

Or

20-10=10

5___> 10-5=5

5---- 5-5=0

Total number of coins=3

Problem 2:

N=41

Coin= {4, 10 ,25}

Solved by greedy approach:

25--- 41-25= 16

10-> 16-10= 6

4-> 6-4=2 3= total number of coins

According to greedy approach, solution does not exist.

(25,4,4,4,4) according to this , solution is exist.

Greedy approach is fail


Solution is exist by DP.

Coin changing problem by DP:

N=4

Changing coin ={1,2,3}

i/j 0 1 2 3 4
1 1 1 1 1 1
2 1 1 2 2 3
3 1 1 2 3 4
0 having no chance : 1

Number of max ways to have change : 1111

22

2 11

31

You might also like