Reference no: EM132139771

Question :

Suppose you are buying stamps to put on a package at the post office.

The postage required to send the package is N dollars. You can buy $1, $7, and $10 stamps. You want to find the minimum number of stamps required so that you have at least SIV worth of stamps. Note that the solution to this problem may not actually be the cheapest solution in terms of dollars: for example, if you need stamps totaling $16, then you can buy a $10 and a $7 stamp, which adds up to $17.

Or you could buy a $10 stamp and six $1 stamps, which adds up to $16. The second solution requires seven stamps, so the first solution is better (even though it is more expensive). However, if there are multiple solutions that use the same number of stamps, then you should return the one that is cheapest.

Design a dynamic programming algorithm that finds the minimum number of stamps required. The input to your algorithm is the total desired postage value N. The output should be the number of stamps required. (You do not have to tell me which stamps were used.)

Part a: Draw the DAG corresponding to this problem. Hint: Let the nodes correspond to different total postage values, and let the edges correspond to different stamp choices.

Part b: Solve the dynamic programming problem using your DAG. Hint: Once you have drawn the DAG correctly, the original problem becomes a very simple graph problem on the DAG.