Suppose you are buying stamps to put on a package at the post office. The postag
ID: 3841979 • Letter: S
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.
Explanation / Answer
Hi, Please find my algorithm.
Given a value V, if we want to make number of stamps for V cents,
and we have infinite supply of each of S = { 1, 7, 10} valued stamps,
what is the minimum number of stmpsa to make the V?
The minimum number of stamps for a value V can be computed using below recursive formula.
If V == 0, then 0 stamps required.
If V > 0
minStamp(stamps[0...2], V) = min {1 + minStamp(V-stamps[i])}
where i varies from 0 to 2
and stamps[i] <= V
The time complexity of above solution is exponential. If we draw the complete recursion tree, we can observer that many subproblems are solved again and again.
Since same suproblems are called again, this problem has Overlapping Subprolems property.
So the min coins problem has both properties of a dynamic programming problem.
Recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner.
Below is Dynamic Programming based solution.
// m is size of stamps array (number of different stamps)
int minStamp(int stamps[], int m, int V)
{
// table[i] will be storing the minimum number of stamps
// required for i value. So table[V] will have result
int table[V+1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i=1; i<=V; i++)
table[i] = INT_MAX;
// Compute minimum stamps required for all
// values from 1 to V
for (int i=1; i<=V; i++)
{
// Go through all stamps smaller than i
for (int j=0; j<m; j++)
if (stamps[j] <= i)
{
int sub_res = table[i-stamps[j]];
if (sub_res != INT_MAX && sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
return table[V];
}