如何購買物品的組合

Question

我試圖找到一種方法來弄清楚（在C++中），給定一個物品的列表與一個不變的價格，一個人有多少種方法可以購買X數量的物品，如果他們有X美元的數額。

到目前爲止，我試圖使用嵌套for循環嘗試和蠻力的解決方案，但是，我覺得我可能會錯過一個非常簡單的解決方案，我似乎無法看到。

任何幫助將非常感激。 謝謝。

Answer 1

這與常見的編程問題非常相似：「有多少種方式可以將Y種類的硬幣與Z值組合成X幣」，即用Y幣類型改變X美元。

這裏有可能被移植到C++的通用解決方案：

I = list of items SORTED from highest to lowest price 
N = number of items bought so far 
M = money left 
S = money to start 

function shop(I, N, M, S): 
    if M < 0: return 0 //we bought something illegally! 
    if M == 0: 
    //If we have no money, we've bought all we could. 
    //Check our condition that num items N = starting money S 
    return 1 if N == S, else 0 
    if I is empty: 
    return 0 //no more item combos, no way to buy things. 
    else: 
    newI = I with first element removed 
    //Every time we want to buy stuff, we have two options: 
    //1. buy something of highest value and subtract money 
    //2. Shop ignoring the next highest value item 
    return shop(newI, N, M, S) + shop(I, N+1, M-(cost of first item), S) 

隨着X元，你開始與呼叫：

shop(I, 0, X, X)