# How can I approach creating an efficient algorithm for maximizing value with these specific constraints?

I'm having trouble coming up with an approach that isn't n^2 for this problem. Here's a contrived, simplified version I've come up with:

Let's say you're a company that needs 4 employees to launch in a new city, a manager, two salespeople, and a customer support rep, and you magically know how much impact every candidate will have and how much salary they require to take the job. Your table of potential employees looks something like this:

``````Name           Position       Salary     Impact
Allison Brown  Salesperson    40,000     9
...etc (thousands of records)
``````

What algorithmic approach can be taken to find the maximum "impact" while still filling all the positions and remaining under, say, a 200,000 budget?

Thanks!

• This is a variant of the well-known Knapsack problem (en.wikipedia.org/wiki/Knapsack_problem). And as Wikipedia states, use dynamic programming, branch&bound or a combination of both. Apr 10 '14 at 5:57
• Just as a remark, I think that your first sentence is not correct. You should consider yourself happy if you find an approach that is n^2, given that a brute force approach has a complexity of 2^n. Feb 4 '15 at 14:42
• @DocBrown That should be an answer =) Apr 5 '15 at 13:18
• Are you doing this many times on the same data set? Do you just need a "good enough" result, not perfection? If both answers are "yes", you can get a quick solution by keeping the data in tables sorted by Impact/Salary and by Impact. Apr 5 '15 at 17:25
• @Ixrec: no, it should not, answers which are not much more than a pointer to a different article are not welcome here on PSE. Apr 5 '15 at 20:34