Algorithm to check sum of numbers from several ranges wanted

Question

i'd like to know if there is more optimal algorithm for the case below than simple iterating over the collection of items.

Suppose there are several items (2-10) with weight defined as range and increment, like
Item1 [0, 50] increment = 5
Item2 [40, 60] increment = 10.

The task is to check if there is at least one combination of weights which sum up to 100. In the example above there are 50+50 and 40+60 combinations.

As the number of items is not big iterating over all items weights wouldn't take much time but maybe there is a better way.

Thanks

UPDATE: i look for algorithm which doesn't require the list of all possible weights or weights sum, i need algorithm which checks if there is at least one combination of weights equals 100 just knowing the range and increment

Answer 1

This problem seems to be a version of the subset sum problem, which is NP-complete. Hence the answer is no, there probably isn't an efficient algorithm in the general case. Some heuristics may help you achieve good results though.

Answer 2

If I'm understanding this right, we're given some total T (with T=100 in this case), and k pairs of ranges and intervals

([x₁,y₁], n₁), ([x₂,y₂], n₂), ..., ([x_k,y_k], n_k)

and for each of them we've got to pick a value

a_i ∈ {x_i, x_i+n_i, x_i+2n_i, ..., y_i}

so that

a₁ + a₂ + ... + a_k = T

So basically, the problem is to find values c_i satisfying

x₁+c₁n₁ + x₂+c₂n₂ + ... + x_k+c_kn_k = T

subject to the constraints

0 ≤ c_i ≤ (y_i-x_i)/n_i for all i.

I believe this is what they call a linear integer constraint satisfaction problem. The general class of approaches for these kinds of problems is called integer linear programming. Such problems are usually NP-complete (though I don't know nearly enough to comment on this specific case), but I think there are still some relatively efficient heuristics.

In fact, this belongs to an even more specific subset of problems, as all the variables c_i can only take a finite number of values (being integers, bounded above and below). Some Googling for CLP(FD) (constraint logic programming on finite domains) might give you an idea of how these are approached in general (though again, this may be a special case with an easier solution that I'm unaware of).