如何计算总和为给定值的值的倍数？

Question

我遇到了一个优化问题，我试图找到加起来特定 $ 值的最佳产品数量。必须选择所有项目并允许重复。例如：

desired total >= 12 and <= 13
hat 
shoes 
tie

结果可能是：

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 它不起作用。

非常感谢任何关于如何使这项工作的指导。谢谢

Answer 1

先说明一下你的需求：

所有项目必须至少选择一次
找到所有可能的结果总和 >= lower_bound 和 <= upper_bound
项目可以重复使用
查找所有组合而不是排列（不关心顺序）

你可以使用回溯来得到你想要的：

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,

希望对您有所帮助，如有其他问题，请评论。 :)

如何计算总和为给定值的值的倍数？

How to calculate multiples of values that sum to a given value?

python

combinations

mathematical-optimization