1

We have n stamps where each stamp i has a specific denomination d(i) and size s(i). All denominations are distinct and we can use stamp denominations multiple times. Now I want to design an algorithm that with given d(i) and s(i) for stamps and a postage amount p, find the minimum total size of stamps that whose denominations will add to exactly p?

I know that it is a dynamic programming problem and also I feel that it is to be solved like knapsack problem. But I am totally confused because here the minimum total size of stamp should add up to p. I came up with the following recurrence and I know that this is not gonna be true because it does not check if the total min size adds up to p:

M(p)=min{M(p-d(i))}+s(i),M(p-d(i))} for i from 1 to n

Also I do not know how to tabulate that(in order to write iterative version of dynammic prog).

My guess is that I have to have a 2-D array with dimensions p and d(i) and each cells fills with s(i).

Improve this question

2 Answers 2

Reset to default
2

Your guess is right. It is two dimensional DP problem. But before we declare that we need to come to a recurrence formula and then we will see how many fields are varying in that formula.

In your problem statement there are two things: 1) Stamp size needs to be minimized. 2) all stamp should add up to sum P. If you are beginner dont think DP bottom up straight away. Think top down recursive approach first which should become easy to think after some practice. In this case, lets say you know solution to N number of stamps. Lets represent this solution to M(d(N), P), which says M is solution out of N stamps that sums up to P. To get recursive relation, think what is if last stamp (Nth) is not part of result then problem will be reduced to finding P out of N-1 stamps. And if last element is present (Nth stamp) problem is to find P - d(N) sum out of N-1 stamps. The recurrent relation of which looks like as:

M(N, P) = Min{ M(N-1, P), M(N-1, P - d(N))}

or in more general sense:

M(i, P) = Min{ M(i - 1, P), M(i - 1, P - d(i))}

As you can see two fields are varying in this recursive formula hence you got to think two dimensional DP.

Take two axis, on X axis take 0 to P all the sum and on y axis take number 0 to N (number of elements). iterative function should look like below.

set all M(0, j) and M(i, 0) = 0 for all i [0, N] and j [0, P]

for: i = 0 to N
   for: j = 0 to P
      for: int k = 0 to j
        if: j - P(k) >= 0 and M(i, j) < M(i-1, j-P(k))
           M(i, j) = M(i-1, j-P(k));


return M(N, P);

Note: i have not mention size for the stamp as it is obvious that field in M will be size for those selected stamps that needs to be minimized.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Following is DP recurrence relation which incorporates both the requirements. First your problem is similar to knapsack problem with only the change that you need to fill knapsack fully here capacity being p and (s(i),d(i)) being the types of items.

DP solution :-

Consider there are n items with (s(i),d(i)) and postage amount p, Valid(n,p) indicates that sub problem has solution which exactly adds up to p :-

DP(n,p) = 0;
Valid(n,p) = 0;

if(Valid(n-1,p)) {

    DP(n,p) = DP(n-1,p);
    Valid(n,p) = true;

} 

if(Valid(n,p-d(n)))  {

  DP(n,p) = min{DP(n,p),DP(n,p-d(n)) + s(n)};
  Valid(n,p) = true;

}

Final Result :

if(Valid(n,p)) {

   return(DP(n,p));

}

else printf("no solution");

DP solution using bottom up :-

Valid[n][p+1] = {false};
DP[n][p+1] = {0};
Valid[0][0] = true;
DP[0][0] = 0;
for(int i=0;i<=p;i++) {

   if(s[0]<=i) {
       if(Valid[0][i-d[0]]) {

        DP[0][i] = s[0] + DP[0][i-d[0]];
        if(s[0]==i)
        Valid[0][i] = true;
       }          
   }
}

for(int j=0;j<n;j++)
    Valid[j][0] = true;

for(int j=1;j<n;j++) {

 for(int k=1;k<=p;k++) {

  if(Valid[j-1][k]) {

        DP[j][k] = DP[j-1][k];
        Valid[j][k] = true;

    } 

    if(Valid[j][k-d(j)])  {

      DP[j][k] = min{DP[j][k],DP[j][k-d(j)] + s[k]};
      Valid[j][k] = true;

    } 

 }

}
Improve this answer

6 Comments

Thanks a lot can you please also say the iterative version of the algorithm?(it is easier for me to understand that)?
Thanks I guess the recurrence relation is : min(i,j)=min{m(i-1,j),m(i,j-Pi)+Si;if j>=pi) but I do not know how to add the condition that check the total value adds up to exaxtly p. what is your idea?
@HamedMinaee I have added a valid array to check if the subproblem makes up exactly the value p-s[i]. If so then only it is accepted as solution. The base condition being Valid[0][p] = true if p%s[0] == 0
@HamedMinaee If there is valid solution to subproblem then solution to the problem is also valid
DP[j][k-d[j]] indicates that we can use the same item j again if feasible so yes the DP takes care of using multiple denomination
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.