*i m very new to dyanmic programing and 0/1 knapsack problem… without seeing tutorial of knapsack problem or without knowing exact algo of knapsack i gave my try… and i am getting AC answer in less no of input but my
program giving time limit exceed, when i am submitting my solution… it means my code is taking too much time …
[problem link geeksforgeeks][1]
here is my code link–[code link][2]
please anyone analyse what is time complexity of program and how u analysed time complexity? and any suggestion to overcome time limit exceed…*
@vijju123 help me
or any small hint to get in right direction and solve it without looking at editorial
[1]: http://practice.geeksforgeeks.org/problems/0-1-knapsack-problem/0
[2]: http://ide.geeksforgeeks.org/e1uBV8
Did you try an iterative approach??
Okay, so i did the problem. Took a lot of thinking (and time) but it turned out to have a simple approach. I will suggest you to follow an iterative approach.
Your code will be really simple if you term of dp table in terms of weight. Look at spoilers below, if you’re doing dp table in terms of weight. I did it by nested loop, outer loop for values and inner loop updating dp, that upto which weight can this value be included.
Spoilers-
-
Click to view
Make sure dp table is 1 indexed. Its best in terms of convenience. The approach is based of including the element where ever possible, if it leads to a higher value than current.(hint- use of max function)
-
Click to view
When will we add the value? When including its weight will still result in total weight less than or equal to w. Hence, can the expression for dp have something to do with (dp[i+weight[i]]+val[i]) ??
-
Click to view
Lets say we include an element of value val[i] and weight w[i]. In expression given in spoiler 2.
, we did dp[i+weight[i]]+val[i]. Will it be worthwhile to loop through all regions W such that 0<=W<=TotalCapacity-weight[i] and update them?? Can we set limits of inner loop using this?
Hint - Updating them will be of use again, in case we come across a smaller weight.
-
Click to view
This spoiler contains the loop i used to fill the dp table.
Click to view
for(i=0;i<n;i++)
{
for(j=0;j<=w-weight[i];j++)
{
dp[j]=max(dp[j],dp[j+weight[i]]+val[i]);
}
}
Okay…posting hints is tougher than posting solution XD. I hope they help you though ^^. If not, i can explain my solution to you.
BTW, i wont lie, i had to look up at the complexity of proposed solution to start. Once i saw proposed solution’s complexity is not linear, then i started thinking in right direction. Else, I felt it was possible in O(N), but couldnt think of anything. After that I tried doing it with dp[n] (failed), dp[w] (0 base index and well…got overwhelemed in thought process). I didnt expect my solution to pass tho, but looking at working i got some confidence ^^
1 Like
@vijju123 bro… did u have knowledge about dynamic programing before attempting this…
Yes. You need to. And it still took me 4 hours. Actually, for some reason, LIS came to my mind here. If you see carefully, the loop structure follows LIS [except that going checking from j=0 to j=i-1, i check from j=0 to j<=w-w[i], and instead of adding just 1 in favourable cases to dp, we add val[i])]
I cannot come up with a O(N) solution tho. Wasted an hour thinking on it. If anyone has a linear solution, i will appreciate that.
i don’t know anything about dp now, that’s why it is causing problem for me… now will try to first learn some basic dp and then implement in knapsack 
thanks for your precious time…
here one question came to my mind, what if i tag someone like u @vijju123 , i think in codechef there is no option of notification in discuss.codechef.com. ,so manually we have to check wheather someone replied to comment or not even he/she tags like @vijju123… am i right?
There IS a notification system, which is exactly the point of tagging, but I have set it off by default. Would have been inconvenient.
Yes, knapsack is not a beginner dp problem. There is a easy section on geeksforgeeks.org , that should give you lots of good problems to practice.