Take the 2-minute tour ×

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.


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

share|improve this question
Simple iterating? what is this simple iterating? As I can think about this there is a brute force or DP not simple iterating. –  Saeed Amiri Dec 26 '11 at 15:42
by simple iterating i mean creation of the list of each item possible weights and then summation of these weights one by one. I suppose you mean the same by brute force –  Melena Jan 12 '12 at 17:10
add comment

4 Answers

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.

share|improve this answer
Interestingly, I believe the conventional subset sum problem on any one of these sets {x,x+n,x+2n,...,y} is at most O(T) for a target sum T. (Maybe even less, but I couldn't do better.) –  Nick Barnes Feb 3 '12 at 0:12
add comment

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

([x1,y1], n1), ([x2,y2], n2), ..., ([xk,yk], nk)

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

ai ∈ {xi, xi+ni, xi+2ni, ..., yi}

so that

a1 + a2 + ... + ak = T

So basically, the problem is to find values ci satisfying

x1+c1n1 + x2+c2n2 + ... + xk+cknk = T

subject to the constraints

0 ≤ ci ≤ (yi-xi)/ni 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 ci 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).

share|improve this answer
add comment

You can build up a set of all the possible weights you can produce. Weights above the total are discarded.

def weight_sum(items, total):
    possible = set([0])
    for weight_range, increment in items:
        new_possible = set(possible)
        for w in xrange(weight_range[0], weight_range[1] + 1, increment):
            new_possible.update(p + w for p in possible if p + w <= total)
        possible = new_possible
    return total in possible

items = [[[0, 50], 5], [[40, 60], 10]]
print weight_sum(items, 100)
-> True
print weight_sum(items, 111)
-> False
share|improve this answer
add comment

Brute force in Python (I assume that each sum must contain weights from all items):

from itertools import product

goal = 100
items = dict(Item1=range(0, 51, 5), Item2=range(40, 61, 10))

print(any(sum(weights) == goal for weights in product(*items.values()))) # True

Where product() is a Cartesian product:

>>> list(product(range(1, 3+1), range(40, 60+1, 10)))
[(1, 40), (1, 50), (1, 60), (2, 40), (2, 50), (2, 60), (3, 40), (3, 50), (3, 60)]
share|improve this answer
add comment

Your Answer


