Given a list of $n$ pairs (cost,points) and number $k$ ($0 \le k$), find the maximum possible sum of points s.t their sum of costs no more than $k$. return the maximum possible sum of points and their corresponding sum of costs.
For example the list $[(5,10),(1,2),(4,3),(6,12),(11,18)]$ and $k=15$, the maximum sum of points with costs no more than 15 is 25 using the first,third and 4th pairs, and therefore we return (25,15).
Note that we can use each pair once but the same pair can appear more than once in the list(and then we can use each of its appearances once).
I was thinking about taking a dynamic programming approach here:
Let $dp[i]$ be the maximum possible of points we can get starting from index $i$ with sum of costs $\le k$, paired with the cost we used to get it.
For the example above: $dp = [(25,15),(20,12),(21,15),(12,6),(18,11)]$. After calculating $dp$ we can return the pair with highest first coordinate.
My problem here is how to calculate $dp$, The only way I tought of computing it was to go from the end towards the beginning while maintaining a second list containing all the possible pairs with costs $\le k$ and in each iteration try to add the current pair's cost to any of them and take the max of the points we found and put it in $dp$.
The problem with this approach is that it the 2nd list's size can be big and therefore the algorithm will be slow.
Is there a way to improve this approach or any other ways to solve this problem?
Thanks in advance.
