# Given a list of pairs (cost,points) and a number k, find the maximum sum of points with sum of costs less than or equal to k

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?
The idea of the dynamic programming algorithm is that if that if $$K(i, c)$$ denotes the maximum sum of points with sum of costs lesser than $$c$$, using only elements of indices $$\{1, …, i\}$$, then: $$K(i, c) = \max (K(i - 1, c), K(i - 1, c - cost[i]) + points[i])$$ (you consider in both option whether to pick item $$i$$ or not).
• Depending on which value is the greatest when computing the maximum, you know if you want to pick $i$ or not. Keep track of that and you will get a list of such $i$'s (and so the sum of points and the sum of costs). Dec 2, 2022 at 19:10