0 - 1 Knapsack (DP)

#1

Why is it failing some test cases?

#2

@Karanveer
Your code was correct. Just perform these steps.

for(int i = 0;i <= n;i++) dp[i][0] = 0;
for(int i = 0;i <= cap;i++) dp[0][i] = 0;

This is being done because the maximum value you can take out of a zero capacity bag is 0 and the
value taken out of 0 items is 0.
If I was able to answer your query, please mark the doubt as resolved.

#3

it is still failing some test cases…

#4

@Karanveer
Will look into that

#5

@Karanveer
You are making an error in printing the values. You are expected to print dp[n][cap] and not dp[n - 1][cap - 1]. This is because the size of your dp array is (n + 1)*(cap + 1).
Just perform this step and it will work out.

If I was able to answer your query, please mark the doubt as resolved.

#6

thanks its working now… But can you please explain that when i initialize the dp array like this dp[n+1][cap+1] = {0}; and then start the loop from 1, then why does that not produce the correct output.

#7

thanks its working now… But can you please explain that when i initialize the dp array like this dp[n+1][cap+1] = {0}; and then start the loop from 1, then why does that not produce the correct output.

#8

@Karanveer
Can you please elaborate a little? I didnt quite get the question.