# Sum of all possible products when each product has a maximum

1. Nov 29, 2013

### Wentu

Hello

I have a set of sets of real numbers greater than 1. Each set can have a different quantity of numbers.
Set A1 {a11, a12,...a1m1}
Set A2 {a21, a22, ..., a2m2}
...
Set AN {aN1, aN2, ..., aNmN}

If I want the sum of all possible products that have one element from each set, that's easy: (a11+a12+...+a1m1)x(a21+a22+...+a2m2)x...x(aN1+aN2+...+aNmN).
But what i interested in is the sum of all possible products that have one element from each set BUT if the product is Higher than K, then the product must be included as K, not as its real value.
Short example:
Set A1 (2,3)
Set A2 (7,9)
K = 20
Usual sum = 14 + 21 + 18 + 27
Sum I am interested in: 14 + 20 + 18 + 20

What's the fastest way to calculate it? is it possible to do this with a neat formula or am I forced to cycle over all combinations?
Thankx

Wentu

2. Nov 29, 2013

### Staff: Mentor

I don't see how to calculate this without any loops. You don't have to consider all combinations - as an example, if a1*a2*a3 > K and you have 10 sets, you can calculate m4*m5*...*m10 combinations at once as they all give K.
On the other hand, if a1*a2*a3 * (maximal element of A4) * ... < K, you can ignore the limit and calculate all sums as well. Starting the loops with a clever choice of sets could save some time, but that depends on the numbers.