-1
$\begingroup$

I recently encountered a coding interview question which is broken down as follows.

You are given an array N which consists of pairs n which consist of a reward and a cost.
You are also given m which is the maximum cost you can incur.

Find the subset of N in which the sum of the reward is maximized and the sum of the cost does not exceed m.

$\endgroup$
2
  • $\begingroup$ What have you tried so far? $\endgroup$
    – Evil
    Sep 20, 2019 at 23:19
  • $\begingroup$ I think I have figured it out. Compute the ratio of reward to cost and sort by that value. Then take the first pairs until the cost limit is reached. Not sure if this is the most optimized but it's certainly better than brute force. $\endgroup$ Sep 21, 2019 at 2:13

1 Answer 1

1
$\begingroup$

This is the Knapsack Problem in disguise. It is an NP-hard problem so do not expect a polynomial time algorithm. However, it has a pseudopolynomial time algorithm (it is polynomial in the instance size and value of the biggest occurring number) and thus has a FPTAS.

Your comment describes a 2-approximation of the problem if you take the maximum of "your solution" and the biggest reward.

$\endgroup$

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.