Knapsack-01 problem

#1

i am getting TLE in some of the test cases.please check my code and guide
is memoization is correct??
or there is any logic mistake??
here is my code

#2

Hey @aditikandhway
The issue with your code is that you are declaring the dp array during each function call because of which the dp values which you calculate are of no significance. Also because of this the time complexity is turning out to be O(2^n). Please approach the question using a 2D dp solution which works in O(n^2) time complexity. If you face any issue in the approach, please revert.

If my answer is able to answer your query, please mark the doubt as resolved.

#3

can you tell me how to approach this question using 2d DP??

#4

Create a 2D matrix of size (n + 1)*(m + 1) where n is the length of the sizes array and m is the capacity of the knapsack. Here, dp[i][j] refers to the maximum values knapsack can store if currently we have considered all the elements from 0 to (i - 1) and only j portion of the entire capacity has been used.
If (j - sizes[i - 1]) >= 0 then dp[i][j] = value[i - 1] + dp[i - 1][j - sizes[i - 1]. The state dp[i - 1][j - sizes[i - 1] refers to the maximum value knapsack can store if currently we have considered all the elements from 0 to (i - 2) and only (j - sizes[i - 1]) portion of the entire capacity has been used beacuse the (i - 1) th object now occupies sizes[i - 1] portion of the knapsack.

If (j - sizes[i - 1]) < 0, the dp[i][j] = dp[i - 1][j]. This is being done because the object under consideration cannot be included in the knapsack.

I hope this does provide u an intuition in the working of the question.
If my answer is able to answer your query, please mark the doubt as resolved.

#5

https://ide.codingblocks.com/s/315401… please check i am getting segementation fault

#6

There was a single issue in your code. While taking input in array a, u were performing the following
cin >> a[n] . This is entirely wrong. Change it to a[i]. Also in case(j - size[i - 1]) >= 0,
dp[i][j] = max(value[i - 1] + dp[i - 1][j - size[i - 1]], dp[i - 1][j]). This is done because we have two ways, either to consider the (i - 1)th element or not to consider it.

If my answer is able to answer your query, please mark the doubt as resolved.