我遇到了一个优化问题,我试图找到合计特定$值的最佳数量的产品。必须选择所有项目,并允许重复。例如:
desired total >= 12 and <= 13
hat $3
shoes $5
tie $2
结果可能是:
1 hat, 1 shoes, 2 tie
2 hat, 1 shoes, 1 tie
这是工作中的发现问题,而不是家庭作业。我在另一个线程中找到了该解决方案,但无法完全解决该问题。
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
print result
它适用于一堆随机数,但是当我从例如
10
到25
并将输入位数更改为浮点数0 < x <= 1.5
无效。非常感谢您提供有关如何进行此工作的任何指导。谢谢
最佳答案
让我先澄清您的要求:
所有项目必须至少选择一次
查找所有可能的结果总和> = lower_bound和物品可以重复使用
找到所有组合而不是排列(不在乎顺序)
您可以使用backtrack获得所需的内容:
def find_all(data, lower, upper):
total = sum([d[1] for d in data])
lower -= total
upper -= total # all items must be selected at least once
if upper < lower or lower < 0:
return []
results = []
def backtrack(end, lower, upper, path):
if end < 0: return
if lower <= 0 <= upper: # satified the condition
results.append(path)
return
if upper >= data[end][1]:
new_path = path[:]
new_path[end] += 1
backtrack(end, lower - data[end][1], upper - data[end][1], new_path) # choose the last one
backtrack(end - 1, lower, upper, path) # don't choose the last one
backtrack(len(data) - 1, lower, upper, [1] * len(data))
return results
测试:
def print_results(results, data):
for result in results:
for count, d in zip(result, data):
print(f'{count}*{d[0]}', end=', ')
print()
print()
data1 = [('hat', 3), ('shoes', 5), ('tie', 2)]
print_results(find_all(data1, 12, 13), data1)
data2 = [('hat', 3), ('shoes', 5), ('tie', 2), ('cloth', 10)]
print_results(find_all(data2, 25, 28), data2)
输出
1*hat, 1*shoes, 2*tie,
2*hat, 1*shoes, 1*tie,
1*hat, 1*shoes, 4*tie, 1*cloth,
2*hat, 1*shoes, 3*tie, 1*cloth,
1*hat, 2*shoes, 2*tie, 1*cloth,
2*hat, 1*shoes, 2*tie, 1*cloth,
1*hat, 2*shoes, 1*tie, 1*cloth,
3*hat, 1*shoes, 1*tie, 1*cloth,
希望对您有所帮助,如有其他问题,请发表评论。 :)
关于python - 如何计算总和为给定值的值的倍数?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/56033259/