WA in knapsack problem.

problem link: http://www.spoj.com/problems/PARTY/


my solution: http://ideone.com/1DbuAF

Problem is,I’m getting a different(least possible) value for the sum of entrance part for the same optimal solution. The problem states that “Achieve the highest possible fun level, and do not spend more money than is absolutely necessary.” which makes me believe that we need to calculate the minimal entrance fee and even the comments from the problem page say so. So my program calculates the minimal entrance fees and prints 36 32 instead of 48 32 and gets WA as expected.

I don’t understand what is actually required and where am I going wrong or how to get it correct. A little bit of clarification would be extremely helpful.
Thank you.

No you are wrong. The aim of the question is to spend the maximum amount of money that is strictly less than the alloted amount while having the most fun. A classical knapsack problem.
The algorithm is as follows assuming u have p parties and n is the maximum amount of money you can spend create a 2D array or vector v. now v(i,j) refers to the maximum fun you can have within the first i parties and with spending exactly j money.
now v[i+1][j]=Max(v[i][j],v[i][j-costof(i+1) party]]+fun in i th party]) . Provided the admission fee in i+1 party is less than n.
Now the answer to the question is the maximum of v[n-1][j] where j varies from 0 to n-1.
For more reference refer here.

hey thanks for your response. The answer that i get for the maximum fun is correct as you can see and i have implemented the 0-1 knapsack problem here. I am having problem calculating the sum of entrance part. I got a suggestion from topcoder which says that “the value of W at which the answer is same as arr[n][W] is the minimum entrance fees at which u are getting the max fun.” Now here is my modified code http://ideone.com/xsywq1

now the answers for the test cases are correct but yet i get WA. Is there anything else that I’m missing out?

//