lixolas's blog

By lixolas, history, 6 years ago, In English

Yup, you read it right ;)

I know this isn't really a big thing, but still is something that might help when you are about to code a DP which has to optimized in memory.

So, take, for instance the Knapsack problem:

Background

You have N items, each with profit Pi and weight Wi. You want to fit the items in a Knapsack with max capacity of B. What is the max profit you can have?

The usual solution for this DP uses 2 dimensions: dp[i][j] stores the max profit using until the i-th item, with total weight j. So we have the following recursion:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Wi] + Pi).

"Ok, but what is this all for anyway?"

So, first notice that we are dealing with 2 dimensions; the first one is just an index for the items, and the second one is the capacity we are dealing with right now. Also, notice that we are only going backwards in the second dimension. Because of this structure, we could replace the classic 2-dimension code by the following:

for(int i=0; i<N; i++) {
    for(int j=B; j>=0; j--) {
        if(j - W[i] >= 0) {
            dp[j] = max(dp[j], dp[j-W[i]] + P[i]);
        }
    }
}

To retrieve the answer, just take max(dp[j]) between all valid j.

This trick only works because we are walking backwards in the weight dimension instead of forwards. So, when we are updating the DP, we won't mess up and risk using the same item twice (which could easily happen if we went forwards with j). This strategy is sometimes useful when you want to use a DP which goes well in time, but not so much in memory =P

This could be used in the recent contest problem 1078B - The Unbearable Lightness of Weights, and this was, actually, my motivation for writing this blog. My AC submission uses this logic: 45977998.

A little down: you can't recover the list of the items by this method, only the rock-solid answer.

That's it, folks! Have a good day/noon/night! ;)

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
6 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

You can still recover the list using dimension compression. The trick actually appeared in one csacademy round iirc.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, that's nice. Didn't know that! Nice to know there's a way for recovering the solution; thanks for posting!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry for necroposting.
      What does it mean by recovering the list of items?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        LOL you are fine. Glad I have email updates turned on. "recovering the list of items" that were selected to be included in the knapsack; in case the problem asks you the items, not only the max value.