There are n tickets numbered from 1 to n. Each ticket has a price given by the array price[] and the number of points that you will get after purchasing the ticket is given in another array points[]. You have x amount of money. You need to find out the maximum number of points you can get.
Constraints are 1<=n<=36 1<=price[i]<=1e9 for all i from 1 to n 1<=points[i]<=1e9 for all i from 1 to n and x<=1e9
I am not able to come up with the optimised approach to the problem. Can someone help me to solve this!!
Just Looking at constraints and problem statement gives me feel of Meet in the middle Algorithm.
Yeah it is. Find all subsets for first half and second half. Now for each subset in the first half let's say it has cost c, you need to find the maximum points you can get in the second half under with cost <=x-c. This can be done with stl sets or something
Thanks!
Isn't that knapsack dp?
Check constraints.
Oh yea. Mb, didn't notice it said 10^9. I guess maybe you could use coordinate compression. (Idk if you'll take my suggestion as I'm only a newbie... :/)
Coordinate compression doesn't work. Worst case you'll find 10^9 distinct elements anyway
But n <= 36 right?
let the price array be $$$1,2,4,8,16,\cdots,2^{n-1}$$$. How many different subset sums do you see here?
Fair point....
In coordinate compression you will need to consider all the number of points that can score which are <=x. So it won't work here.
Knapsack doesn't require considering all points though, Don't you just need to do a coord-compression and then do the mitm knapsack dp?