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.

  • $\begingroup$ What have you tried so far? $\endgroup$ – Evil Sep 20 '19 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$ – Kyle Brainard Sep 21 '19 at 2:13

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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