如何获得所有可能的产品价格组合以达到目标成本？

Question

假设我有一个包含三种产品（A、B、C）的列表。每种产品都有一个价格。给定一个总费用，我想找到所有可能的产品组合，使它们的总价正好等于这个费用。

到目前为止，我尝试了一些方法，比如：

for price in product:
    ret = []
    for i in range(int(totalCost / price), -1, -1):
        ret.append(i)
        for c in range(1, len(products)+1, 1):
            ret.append(int(products[c-1][1]/products[c][1]))

但是我在这里遇到了困难。这种方法可以给我一些可能的组合，但它只会包括列表中当前位置之后的产品。它不会回头去包含列表开头的产品，因此无法得到所有的组合。

我需要做些什么才能得到所有的组合呢？

Answer 1

itertools模块提供了一些组合生成器，可以帮助解决类似的问题：

>>> from itertools import *
>>> prices = dict(a=10, b=15, c=8, d=2, e=5)
>>> total_cost = 20
>>> for r in range(1, 30):
        for t in combinations_with_replacement(prices, r):
                cost = sum(prices[p] for p in t)
                if cost == total_cost:
                        print t

Answer 2

def possibilities(available_products, target_price):
    if target_price == 0 or not available_products:
        return []
    this_price = available_products[0]
    remaining_products = available_products[1:]
    results = []
    for qty in range(1 + target_price / this_price):
        remaining_price = target_price - qty*this_price
        if remaining_price == 0:
            results.append([qty] + [0] * len(remaining_products))
        else:
            for option in possibilities(remaining_products, remaining_price):
                results.append([qty] + option)
    return results

这会给你：

pprint.pprint(possibilities([1, 2, 5], 10))
[[0, 0, 2],
 [0, 5, 0],
 [1, 2, 1],
 [2, 4, 0],
 [3, 1, 1],
 [4, 3, 0],
 [5, 0, 1],
 [6, 2, 0],
 [8, 1, 0],
 [10, 0, 0]]