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:
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 ?
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).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 ?
Thank you. Alas I am not good at Java. So several notes.
-1
? Seems you print some abstract negative number in such a case.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.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.num*
is changed in the fuction $$$go()$$$. So you are setting the value for the other state in the very end of $$$go()$$$:Thanks a lot for this detailed explanation, the last one was my problem.