用于检查所需数个范围的数字总和的算法

Question

我想知道下面的案例是否有更优化的算法,而不是简单地迭代项目集合.

假设有几个项目(2-10),其权重定义为范围和增量,如
Item1 [
0,50 ]增量= 5 Item2 [40,60]增量= 10.

任务是检查是否存在至少一个总和为100的权重组合.在上面的例子中,有50 + 50和40 + 60种组合.

由于项目数量不是很大,所有项目的重量都不会花费太多时间,但也许有更好的方法.

谢谢

更新:我寻找的算法不需要所有可能的权重或权重总和列表,我需要算法检查是否至少有一个权重组合等于100只知道范围和增量

Answer 1

您可以建立一组您可以产生的所有可能的权重。超过总重量的重量将被丢弃。

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