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