In the above code, what i m doing is at any particular idx of my weight array … either I pick that stone or leave it with picking has a condition that the weight of that stone should be less than the unused capacity and that color is not picked yet …
I am not able to decide the states of dp for problem … what i m thinking is of 3-d dp … curIdx … cur_leftCapacity … and cur_leftColors
Colorfull Knapsack .... 1/4 testcase not passing
can you pls let me know what is wrong with my logic in code
I also have used classical 0-1 knapsack concept
@prabh1601
it is bit different from o-1 knapsack. here dp[i][j] is maximum weight possible when i different colours are considered . so u need to maintain a vector of vector where v[i] conatins all weights whose colour is i and then apply standard knapsack.
also pls explain ur approach
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.