0

At a career fair, I was asked the following tough question(not exactly as below, I stripped out the story and expressed the problem (more or less) formally).

Given number K, and a finite list of pairs L = < (a,b), (c,d), (e,f) > where each pair p consists of two numbers n1 and n2. Find the the list R where the sum of the n1 values of all its pairs is the greatest and the sum of all the n2 values of its pairs is less than or equal to K. In the list R, pairs can repeat.

So for example, if your K is 10 and you have the list of pairs L as <(3,2) , (1,7), (4,6) >, then the result would be R = < (3,2), (3,2), (3,2), (3,2), (3,2) > so that the sum of all n1 values would be 3 + 3 + 3 + 3 + 3 = 15 and sum of all the n2 values would be 2 + 2 + 2 + 2 + 2 = 10. This would be correct solution as opposed to something like <(3,2), (3,2), (4,6)> (n1 sum is 10; n2 sum is 10) or like <(1,7), (3,2)> (n1 sum is 4; n2 sum is 9) whose n1 sums are not the maximum possible.

I described an approach where I would essentially enumerate all possible combinations of pairs whose n2 values would sum to number less than or equal to K and pick the combination with highest n1 sum. Enumeration could be done by incrementally subtracting from K, each of n2 values from pairs in the given list L.

Is there a better way to do this ?

Improve this question

2 Answers 2

Reset to default
1

This is the "unbounded knapsack problem". It's NP hard, so there's no (known) polynomial solution, but there's a known pseudo-polynomial time solution if the n2 and K are integers, which you can find here: https://en.wikipedia.org/wiki/Knapsack_problem#Solving

The dynamic programming solution described above, is to compute, for each capacity k, 0<=k<=K, and for each prefix of the list L, the largest value of sum(n1) such that the sum(n2)<=k.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

The important insight, I believe, is to note that the critical factor is the ratio of the two numbers, not their difference. K is your budget; n2 is the cost of each item, and n1 is its value. You need to maximize the value within your given budget.

Sort the list descending by the n1/n2 ratio. Apply the canonical recursion program (see the generalized "making change" problems) to explore the solution space. If it's easier, sort descending by n2 alone; that will make it match the implementation of the coin problem more closely, but at the cost of more search for the optimal solution.

Note that you can prune recursion two ways:

  1. The remaining pairs have a ratio too low to exceed the current best solution.
  2. The next pair evenly divides the remaining budget: with a ratio-sorted list, that must be the optimal solution.

Is that enough of a hint to get you unstuck?

Improve this answer

2 Comments

Can you please elaborate about the "Apply the cannonical recursion program..." part ? So once I have the set of ratios of n1/n2, how would I apply recursion to that ?
What don't you understand about the recursion in the coin-change problems?

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.