how to design dynamic programming algorithm for the following

Question

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).

Answer 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;

    } 

 }

}

Answer 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.