我正在尝试找到一种方法来计算(在 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)
关于c++ - 如何购买元素的组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6966569/