检查多个范围内的数字总和的算法
检查多个范围内的数字总和的算法
提问于 2011-12-26 22:19:02
我想知道对于下面的情况，是否有比简单地迭代项目集合更优的算法。
假设有几个项(2-10)的权重定义为范围和增量，例如
Item1 0，50增量=5
Item2 40，60增量= 10。
任务是检查是否至少有一个权重组合的总和为100。在上面的示例中，有50+50和40+60的组合。
由于项目的数量不大，迭代所有项目的权重不会花费太多时间，但也许有更好的方法。
谢谢
更新:我寻找不需要所有可能的权重或权重总和列表的算法，我需要检查是否有至少一个权重组合等于100的算法知道范围和增量
回答 3
Stack Overflow用户
发布于 2012-02-01 17:14:17
这个问题似乎是的一个版本，它是NP完全的。因此答案是否定的，在一般情况下可能没有有效的算法。不过，一些可能会帮助您获得好的结果。
Stack Overflow用户
发布于 2011-12-26 23:57:08
您可以构建一组您可以生成的所有可能的权重。超过总数的权重将被丢弃。
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)
-> FalseStack Overflow用户
发布于 2011-12-27 00:14:37
Python中的蛮力(我假设每个和必须包含所有项目的权重)：
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其中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)]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8636547
复制相关文章
相似问题
腾讯云开发者
