c++ - 如何购买元素的组合

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)