商品の購入方法の組み合わせ

Question

私は（C++で）一定の価格を持つ商品のリストを得て、X個の商品を購入できる方法を見つけようとしています金額

これまでのところ、ネストされたforループを使用して試してみようとしましたが、私には見えない非常に単純な解決策が見当たりません。

ご協力いただければ幸いです。おかげさまで

Answer 1

これは一般的なプログラミングの質問に非常によく似ています。「YタイプのコインをZ値と組み合わせてXドルを作るにはいくつの方法がありますか？ここで

C++に移植することができ、一般的なソリューションです：Xドルで

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) 

、あなたが呼び出しでオフを開始：

shop(I, 0, X, X)