Need help again!
Here’s my code to SPOJ PARTY problem (0-1 knapsack).
The code seems to work fine (But gives TLE), I want to further optimise it by memoisation.
Can anyone please guide me on how to do that?
PS: I did use a dp array to implement memoisation but it seems to give wrong answer.
Thanks in advance 
Here is the link of full explanation of this question. It also contain an optimisation techniques. So please have a look at this.
If still you would not able to get the logic then comment here. i will try to debug your code!
I don’t think you’re memoizing the DP states.
node l = solve(pos+1, cur+a[0][pos]);
node r = solve(pos+1, cur);
You’re simply calling the functions without checking if they have already been computed. Please try to memoize that part and submit again, good luck!
First, I want to clarify you that both of your solutions are wrong. I will explain both solutions one by one.
Recursive Solution
Your recursive solution is wrong because you are only checking a maximum value of fun, but what is your answer if there are more than one solutions of getting maximum fun value. In such cases, your solution may give wrong answer depending on order of input.
I will give you an example where your solution gives wrong answer:
40 5
12 10
16 10
20 10
24 10
8 3
0 0
In above input, your solution is giving output : 40 23. But, the correct answer is 36 23.
So, in order to get a correct answer, you also need to consider the minimum value of fee.
Solution based on Dynamic Programming
In your DP solution, your DP state is wrong. You are only considering pos as your state, but you missed to add the state cur in your DP. i.e you need to take 2-state DP or 2-D Dp. Why?. Because your recursive function is not depends only on one argument i.e pos, but it also depends on cur. You are calling function two times keeping same pos value, but different cur value. It means that there are two possible values for same pos.
So, finally, you need to add above two changes in order to get accepted. I am providing you a link of correct answer. I didn’t write a complete new solution, but I added the above two functionality in your code so that you can understand it easily.
Actually mine is a recursive solution, and both of these links provide an iterative one (I already know the iterative approach).
The problem is that I cannot optimise my code using some array to store previously calculated results, it gives WA.
Can you tell how are you trying to fill the dp table?
I am not filling any table!
I created a recursive solution. I just want to optimise it.
Okay, lol, I got confused seeing that line stating you tried dp solution.
You have initialised the DP[] array but you didn’t use it in your program. Hence it’s obvious that you will get TLE.
Thats what I was asking
I did use the dp array first but was giving wrong answer. I think I did something wrong. You can try for yourself. It was not working.
Here’s the memoized version JG1Bu0 - Online C++ Compiler & Debugging Tool - Ideone.com
I did memoize but it was giving wrong answers. You can try for yourself.
Here’s the memoized version JG1Bu0 - Online C++ Compiler & Debugging Tool - Ideone.com
@bansal1232, hey bro! See if you can help that guy over there as well.
Most Frequent Element (MFREQ) - Getting wrong answer - general - CodeChef Discuss
I am out of ideas for that one, see if you can help him.