0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Please don't delete your question after receiving an answer. Part of our mission is to build up a high-quality archive of knowledge, in the format of questions and answers that will be useful not only to you but to others in the future. Answerers may be answering from that perspective, so it can be considered impolite to delete the question after receiving an answer. $\endgroup$
    – D.W.
    Dec 9, 2022 at 0:47

1 Answer 1

1
$\begingroup$

Your problem is the Knapsack problem. It is already well documented. It has a pseudo-polynomial time algorithm, and a FPTAS.

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).

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Dec 2, 2022 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.