鉴于不同高度的堆叠，我如何选择每种可能的组合？

输入：总成本。鉴于不同高度的堆叠，我如何选择每种可能的组合？

输出：给出所需成本的所有级别组合。

每个堆栈的每个级别的开销都不同（堆栈1中的级别1与堆栈2中的级别1不相同）。我有一个功能，可以根据我手动输入（硬编码）的基本成本（级别1）将级别转换为实际成本。

我需要找到给我输入成本的级别组合。我意识到有不止一种可能的解决方案，但我只需要一种方法来迭代每种可能性。

以下是我需要：

输入= 224，这是解决方案的一个： these are the costs

我做一个简单的程序，需要选择不同的水平堆栈然后计算成本，并且我需要知道存在的每一个可能的成本......每个堆栈的每个级别花费不同数量的金钱，但这不是问题，问题是如何为每个堆栈选择一个级别。

我大概解释了非常含糊，所以这里的图片（你要原谅我那可怜的绘画技巧）：

these are the maximum levels

因此，所有堆栈有0级，0级始终花费0钱。

附加信息：

我有称为“maxLevels”的阵列，该阵列的长度是堆叠的数量，并且每个元件是在该堆叠中的最高级别的数目（例如，maxLevels [0] == 2）。
您可以从第1级进行迭代，因为级别0根本就不重要。
所选级别应保存在与maxLevels（相同长度）类似的数组中（名称：“currentLevels”），但不包含堆栈的最大级别，它包含选定的堆栈级别（例如：currentLevels [3] == 2）
我在C++编程，但伪代码是罚款以及
这不是功课，我做它的乐趣（这是基本的。游戏）

来源

2011-12-22 corazza

我重新阅读问题几次，我在努力理解它。你能否提供一个具体的例子，显示输入，输出和计算输出的步骤？ – NPE 2011-12-22 11:05:08

我不认为你会从中得到任何东西......只有输入是成本，每个堆栈的每个级别加起来有点，所以程序的任务是找到不同级别的精确组合，以便它匹配成本。我马上回来，我会编辑这个问题！ – corazza 2011-12-22 11:07:56

'（currentLevels [0] + currentLevels [1] + currentLevels [2] + ...）== requested_cost'这是你想实现的吗？或者5级的成本可能不同于5？ – Baltram 2011-12-22 11:15:58

我不确定我是否理解这个问题，但这里是如何通过从每个st中选择一个项目的所有可能的组合ACK（在这种情况下，3 * 1 * 2 * 3 * 1 = 18的可能性）：

void visit_each_combination(size_t *maxLevels, size_t num_of_stacks, Visitor &visitor, std::vector<size_t> &choices_so_far) { 
    if (num_of_stacks == 0) { 
     visitor.visit(choices_so_far); 
    } else { 
     for (size_t pos = 0; pos <= maxLevels[0]; ++pos) { 
      choices_so_far.push_back(pos); 
      visit_each_combination(maxLevels+1, num_of_stacks-1, visitor, choices_so_far); 
      choices_so_far.pop_back(); 
     } 
    } 
}

您可以替换visitor.visit，不管你想要做的每个组合，使代码更具体。我用了一个矢量choices_so_far而不是你的数组currentLevels，但它也可以和数组一起工作。

来源

2011-12-22 11:15:49

嗨，我对C++很陌生，你能用伪代码重新编码吗？ size_t是什么意思？星星和“＆”符号是什么？与指针有什么关系，我猜？我认为它可以做得更简单...什么是“访客”呢？一个东西？我完全迷失在“std :: vector ＆choices_so_far”...另外：“maxLevels + 1”，是不是一个数组？你如何将1添加到数组中？ – corazza 2011-12-22 21:32:08

嘿，我想我明白了。在本质上，我的解决方案与您的解决方案类似，因为我也使用递归，所以我接受了您的答案，因为您有我的想法。谢谢。 – corazza 2011-12-24 19:14:25

这很简单，如果我已经正确地理解了它。最低成本是0，最大成本只是堆栈高度的总和。要达到这些限制之间的任何特定成本，您可以从左侧开始，为每个堆栈选择最大级别，直到达到目标，然后为其余堆栈选择级别0。（如果你超出目标，你可能需要调整最后一个非零堆栈。）

来源

2011-12-22 11:35:28 TonyK

不，情况并非如此。确切的成本是不同层次的不同层次的组合。请看新图片。 :) – corazza 2011-12-24 08:58:04

那么在那种情况下，你的问题是NP-完全的，因为如果每个堆栈的高度为2，它就会减少到背包问题。这意味着在实践中，如果堆栈数大于约30或40 - 请参阅http://en.wikipedia.org/wiki/NP-complete。 – TonyK 2011-12-24 14:11:55

我不会有任何问题。正如我所说，这是一款游戏，目标是计算某些玩家的研究成果。有16个研究在这个游戏中，因此我使用了16个堆栈。每项研究都有一个层次，每个层次的成本是前一个层次的两倍，第一个层次是该研究的基本成本。我想，尽管它运作不好（但不是这一部分，我确实选择了每种可能性）。在我想出来之后，我很快就在全球积分榜上排名第一的球员进行了测试，并且在几秒钟内就给出了结果。 – corazza 2011-12-24 19:09:20

我解决了它，我想。 @Steve Jessop给了我使用递归的想法。

算法：

circ(currentStack) 
{ 
    for (i = 0; i <= allStacks[currentStack]; i ++)   
     if (currentStack == lastStack && i == allStacks[currentStack]) 
      return 0; 
     else if (currentStack != lastStack) 
      circ(++ currentStack); 
}

来源

2011-12-24 19:24:35 corazza

鉴于不同高度的堆叠，我如何选择每种可能的组合？

回答

相关问题