1
$\begingroup$

I have recently been focussing on DP formulation and space optimization in dynamic programming of some problems.
I have gone through the standard questions such as 0-1 Knapsack and Coin Change problems.

In the space optimization part, I haven't understood in which order should I fill the table to get the desired result. For instance, In the above 0-1 Knapsack Problem, which asks about max possible sum of values for a weight of at most w.

vector<int> dp(w + 1); // dp[j] max value that can be obtained with weight exactly j
  for (int i = 0; i < n; i++) {
    for (int j = w; j >= weight[i]; j--) // iterating from right to left here
      dp[j] = max(dp[j], val[i] + dp[j - weight[i]]);
  }

In the above snippet why the ordering is important? I am confused because for the space-optimized version of coin change problem mentioned above we iterate from left to right to get total no. of ways to get change, it goes as @qqibros answer shown here

 vector<int>dp(x+1); // dp[i]- no of ways to get coins with value exactly i
for(int i=0;i<n;i++){
  for(int j=a[i];j<=x;j++){ // iterating from left to right here
    dp[j]+=dp[j-a[i]];
  }
  cout<<dp[x]<<endl;

But if I change the above coin change problem adding the constraint that every coin can only be used exactly once, I should iterate from right to left to get the required answer.
For example,N = 4 and S = {1,2,3}, only one solution {1,3} so the output should be 1. And For N = 10 and S = {2, 5, 3, 6}, still only one solution {2, 3, 5} and the output is 1.
Just changing the line from for(int j=a[i];j<=x;j++) to for(int j=x;j>=0;j--) gives the answer.

I am not able to visualize or interpret correctly how ordering changes the value as in both cases the value only depends on previously stored values.

$\endgroup$
0
$\begingroup$

The difference is whether the solution to the "add element i" subproblem being considered (dp[j - weight[i]] or dp[j-a[i]], as the case may be) allows or forbids a contribution from the current element (value of i).

When the inner loop moves right-to-left, at the time dp[j - weight[i]] is evaluated, that table entry has not yet been updated in this iteration of the outer loop, so it definitely does not include a contribution from element i. Thus the candidate solution having value val[i] + dp[j - weight[i]] includes exactly one copy of element i (and the other candidate solution, dp[j], includes exactly zero copies of it).

OTOH, when the inner loop moves left-to-right, at the time dp[j - weight[i]] is evaluated, that table entry has already been updated in this outer loop cycle, so it may represent a solution that already contains an element i, to which we are now considering adding a second element i. In fact it may already contain multiple copies of element i, since that table entry may have been computed as the result of choosing val[i] + dp[j - weight[i] - weight[i]], etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.