Mr.Awesome's blog

0/1 Knapsack and colored items with conditions
By Mr.Awesome, history, 3 years ago, In English

Hello cf,

I'm trying to solve this 0/1 Knapsack problem:

We have N items with each item characterized by weight, price and color (white, blue, red or black).

We have to choose 12 items with maximum total price such as the sum of their weights is <= W and the choosed items fullfill these conditions:

  • only 1 white item
  • between 3 and 5 blue items
  • between 3 and 5 red items
  • between 1 and 3 black items

I tried this backtracking solution (take or leave current item and continue) wich work fine:

Backtrck solution

This work fines but with an exponential complexity so I tried to add memoization (caching: dp[i][currWeight][numW][numBlue][numR][numBlack]) but it doesn't work anymore.

Can any body explain why the memoization doesn't work here, or share his personal approach to solve this problem ?

Costraints:

N <= 100 W <= 1000

PS I've seen this problem somewhere before but I don't have a link, can anybody provide a link of a similiar problems ?

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

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

it doesn't work anymore

What do you mean? WA? You can give us the code with memorization and actual input case. TLE? You can optimize your code in many ways (together with bottom-up approach).

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

    Backtrack without memoization, gives correct answer: https://ideone.com/aPdZjZ

    Same code and input but with memoization gives WA: https://ideone.com/wPqxBG

    You can generate smaller input and you will see that backtrack work but not memoization, weird, Why ?

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

      Thank you. Alas I am not good at Java. So several notes.

      • What should you print if there are no such 12 items? -1? Seems you print some abstract negative number in such a case.
      • For dp[numW][numBlack][numR][numBlue][id][curW] you have a nonnegative value if it is possible to reach this state and a negative value otherwise. No need in the strange constants like $$$-10000$$$, $$$-1000000$$$ etc.
      • Before adding items[i].value + go( i + 1, numW, numBlue, numR, numBlack, (items[i].cost + currSpent)) you should check that the fuction $$$go()$$$ returns nonnegative value. Otherwise you can turn the initially negative value into positive value by successive summing-up. I do not know the problem's limits. Maybe the constant -10000 is small enough, maybe not.
      • And the error itself. The value of one of the variables num* is changed in the fuction $$$go()$$$. So you are setting the value for the other state in the very end of $$$go()$$$:
              return dp[numW][numBlack][numR][numBlue][i][currSpent] =
                res;
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot for this detailed explanation, the last one was my problem.

        → Reply