当前位置：文江博客话题详情

如何购买物品的组合

发布于 2024-11-28 09:00:00 字数 173 浏览 4 评论 0原文

我试图找到一种方法来计算（在 C++ 中），给定一个价格不变的物品列表，如果一个人有 X 美元，他可以通过多少种方式购买 X 数量的物品。

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

任何帮助将非常感激。谢谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

吲‖鸣 2024-12-05 09:00:00

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

This is very similar to the common programming question: "How many ways can you combine Y types of coins with Z values to make X dollars", i.e. make change for X dollars with Y coin types.

Here's a general solution that could be ported to 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)

With X dollars, you start off with the call: