如何获得每种可能的产品价格组合列表以达到目标成本？

Question

假设我有三个产品的列表(A,BC).每个产品都有价格.考虑到总成本,我想找到所有可能的产品组合,使其完全等于该成本.

到目前为止,我尝试过这样的东西:

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

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]]