Colorful Knapsack problem

#1

my top down approach fail for only one test.
anyone please figure out. what’s wrong.

#2

Hi, according to me there is a flaw in your implementation. You keep track of the following dp state dp(i, knap) where i means you have processed all stones from i to n-1 and you have the remaining capacity knap. Imagine a scenario in which you reach the state dp(i,knap) having collected a red and a green stone(lets say there are three color RGB stones), you will calculate dp(i,knap) and store it. Now lets say you reach the state dp(i,knap) again but this time with a different set of collected stones(lets say only a blue color stone). This time you do not recalculate dp(i,knap) as it is not -1. It is possible that this subset of stones(blue instead of red and green) might have lead you to an overall better solution but your implementation simply dropped it from consideration.

Short explanation : The state that you have used in your dp is not a unique state.

Let me know if this helps.

#3

Also thanks for the well commented code, totally appreciated :slight_smile:

#4

thanks for finding flaw in my implementation.
yes state that i have used in my dp is not a unique state.

1 Like