Pfthb

I'd like some help to find the good algorithm for a problem but I can't even figure out how to abstract this problem so I'll write this question as en example of what I want.

Say I have a list of items of 2 types (A and B) which all have a value. The list looks like this :

1. A1 : 10


2. B1 : 11


3. A2 : 9


4. B2 : 6


5. B3 : 4

My problem is that I want to make as many groups of items as possible for the following rules :

• there must be at least 1 type A item and 1 type B item


• the sum of the values of each group must be at least 20

The output of the algorithm should be :

1. A1 + B2 + B3


2. A2 + B1

Parameters of the problem may vary :

• this list itself of course (number of items, values, ...)


• the number of item types (from 1 to a lot)


• the number of items required per type (I may want at least 2 items from A and 3 items from B)


• the minimum required value sum

I'm almost sure such algorithm exist, it makes me think of the Knapsack problem but I actually don't even know what to search.

It can easily be solved by a mathematical constraint solver:

Let's use following terms:

• @A = number of items with category A


• @B = number of items with category B


• n = min(@A, @B)


• G_j = sum for i = 0 to @A of ( α_j_i * A_i) + sum for i=0 to @B of ( β_j_i * B_i )

Then the following equations must hold in order to have a valid solution:

• G_j is either 0 OR G_j is larger than 20


• min(α_j_0 ... α_j_@A ... β_j_0 ... β_j_@B) is either 0 or 1


• sum(α_0_0 ... α_0_n) is 1 (each A is used once)


• sum(β_0_0 ... β_0_n) is 1 (each B is used once)

And then we simply maximize

T = sum for i = 0 to n of 2 ^ G_i - 1

Which will add a 0 for each empty group, and a larger value for each non-empty group.