Algorithm to find best in class of groups with weighting?

Question

I have widgets and a single widget will have attributes of:

Name
Weight (decimal from 0-1)
Group (letter A-F)
Price (an integer from 1 - 100)

I must pick one widget from each Group (A-F) for a total of 6 widgets. How do I write an algorithm to find the 6 widgets that give me the aggregate highest Price while at the same time keeping the aggregate Weight less-than or equal to 1? Obviously, a lot of combinations will have an aggregate weight less than 1, but I need to come up with a way to get the combination that ALSO results in the highest Price. I suppose I could solve this with a Monte Carlo simulation, but I'm hoping there is a better way.

Answer 1

This is somewhat reminiscent of the "Knapsack problem". As we know, it is NP-complete, so no algorithm exists to solve it fast. I am not going to try to prove that this problem is NP-complete, but it certainly looks that way.

You can however solve it in exponential time like this:

• Generate all combinations (this will be $n_A * n_B * \cdots * n_F$ combinations where $n_A$ i s no. of elements in $A$ and so on)

• sort combinations by aggregate price

• pick the first combination with weight $\leq 1$

Edit: This is in fact the equivalent of the so-called "Multiple choice Knapsack problem". There seems to exist $O(n)$-time algorithms for this using linear programming. You can read about some of their implementations in this paper by David Pisinger: link

Answer 2

I agree with @user126540 that this is exactly a multiple-choice knapsack problem. I just want to make some suggestions about how to quickly filter the lists of possible widgets down to a better set. In doing so, you'll reduce the complexity of the problem for whatever algorithm you have.

Since you want highest price with the lowest weight, you can remove any item from the group that is either heavier than another object for a given price, or has a lower price for a given weight. In other words, you want the Pareto Frontier of maximizing price and minimizing weight (within each group).

This will remove potentially optimal combinations from your population, but the combinations would only be duplicates of the best price, at a higher weight. To give an example, if you have two widgets with (price,weight) of (10,5) and (10,6), then you'd never want the second one. That's because it's heavier without giving any additional benefit in price.

Another way to filer (that is complimentary) is to take advantage of your 1 item per group constraint. For each group, find the lightest possible item and the heaviest possible item. Then, combine the heaviest item from one group with the lightest items from all other groups. If the weight of that combination violates your constraint, then there is no way for the heavy item to be feasible. Repeat this within the group until the heaviest item is feasible. Then repeat for each group.

These operations should be pretty quick. For 9 groups with at most 30 items, you're looking at 4185 (worst case) comparison operations for the first part, and only 270 comparisons for the second.

From there, solving the problem with a standard multiple-choice knapsack algorithm proceeds just the same.