c++ - 如何购买物品的组合

我试图找到一种方法(在c++中)，给定具有恒定价格的商品列表，如果一个人拥有X数量的美元，他们可以用多少种方式购买X数量的商品。

到目前为止，我已经尝试使用嵌套的for循环尝试对解决方案进行暴力破解，但是，我觉得我可能缺少了一个似乎看不到的非常简单的解决方案。

任何帮助将不胜感激。
谢谢。

最佳答案

这与常见的编程问题非常相似:“您可以用多少种方式将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)