Как рассчитать кратные значения, которые суммируются с данным значением?

Question

У меня проблема с оптимизацией, когда я пытаюсь найти оптимальное количество продуктов, которые добавляют определенную стоимость в $. Все элементы должны быть выбраны, и повторение разрешено. Например:

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 не работает.

Любое руководство о том, как заставить это работать, очень ценится. Спасибо

Answer 1

Позвольте мне сначала уточнить ваше требование:

1. все элементы должны быть выбраны хотя бы один раз
2. найти все возможные результаты суммирования> = lower_bound и <= upper_bound </li>
3. элементы могут использоваться повторно
4. найти все комбинации вместо перестановок (не волнует порядок)

вы можете использовать возврат, чтобы получить то, что вы хотите:

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, 

Надеюсь, что это поможет вам, и прокомментируйте, если у вас есть дополнительные вопросы. :)