Question 1: Consider the table below for making change using dynamic programming

Question

Question 1:Consider the table below for making change using dynamic programming. Use the given denominations, and complete the empty cells on the right in order to calculate the optimal way of making change for 10 (units).

Question 2: Consider the table from question (1). Now extract the optimal change for 10 (units): which coins do you use?

Question 3:Now try a new coin system: [1,3,4]. (a) Make change for 6. Show your table. (b) Extract your answer: which coins do you use? (c) Would the greedy algorithm have given the same answer?

Amount:

0

1

2

3

4

5

6

7

8

9

10

d1=1

0

1

2

3

4

5

6

d2=4

0

1

2

3

1

2

3

d3=6

0

1

2

3

1

2

1

Amount:

0

1

2

3

4

5

6

7

8

9

10

d1=1

0

1

2

3

4

5

6

d2=4

0

1

2

3

1

2

3

d3=6

0

1

2

3

1

2

1

Explanation / Answer

take help from this

http://link.springer.com/chapter/10.1007/978-1-84800-070-4_8#page-1

http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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