鑑於不同高度的堆疊，我如何選擇每種可能的組合？

輸入：總成本。鑑於不同高度的堆疊，我如何選擇每種可能的組合？

輸出：給出所需成本的所有級別組合。

每個堆棧的每個級別的開銷都不同（堆棧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

鑑於不同高度的堆疊，我如何選擇每種可能的組合？

回答

相關問題