確定最大樂趣的算法

問題本身可以找到here。其要點是貝西騎着過山車，但她頭暈目眩。在不超過她的「暈眩極限」的情況下，她可以擁有的最大樂趣是多少。輸入包括：確定最大樂趣的算法

「NKL

其中N（1≤N≤1,000）是部分的在該特定過山車的數量; K（1≤ķ≤500）的量如果Bessie在任何路段上閉着眼睛，頭暈會降低;而L（1≤L≤300,000）是Bessie可以忍受的頭暈的極限 - 如果她的頭暈比L大，貝西將會生病了，那並不好玩！

接下來N行中的每一行都會有兩個整數：

其中F（1≤˚F≤20），殼牌得到，如果她讓她的眼睛上那款開放，d的增加Bessies總樂趣（1≤d≤500）增加如果她在該部分保持睜大眼睛的話，可以使她頭暈目眩。該部分將順序列出「

我的算法來解決這個看起來是這樣的：。。？

 cin >> N; // sections 
     cin >> K; // amount dizziness can go down 
     cin >> L; // dizzy ceiling 
     belowL = L; // sets the amount of dizzy left 

     for (int i = 0; i < N; i++) { 
      cout << "\n" << i; 
      cin >> F >> D; // fun increase and dizzy increase 
      if (D < belowL) { 
       if (F >= D) { 
        funTotal += F; 
       } 
      } 
      else { 
       belowL -= K; 
      }

然而，這並不總是產生正確的結果有什麼問題應該挑有趣的選項，除非它會把貝西在病門檻，有沒有更好的方式來做到這一點？

來源

2012-02-15 Linell

我很好奇爲什麼有人投票結束這個，它措辭相當好，並有一個鏈接到原來的問題以及。：p我沒有時間閱讀它，但如果我這樣做，它看起來像一個有趣的問題！ – 2012-02-15 20:26:49

你應該尋找最大限度發揮樂趣的方法，但目前你只是想盡快獲得儘可能多的樂趣。 – 2012-02-15 20:28:50

讓我想起[RollerCoaster Tycoon]（http://en.wikipedia.org/wiki/Roller_Coaster_Tycoon）。當客人離開過山車並摔倒在人行道上時，我喜歡它。 – 2012-02-15 20:30:21

因此，而不是給你的代碼這裏是對問題解決方案的一種解釋。

基本的方法是使用動態編程來解決，因爲這會減少到所謂的Knapsack problem。這樣想一想，她的頭暈是她一次可以攜帶多少東西，而樂趣就是她想要最大化的東西（相比之下，她說的是她在袋子裏攜帶的「物品」的價值）。現在我們想要做的就是從過山車（袋中最有價值）中獲得最大的樂趣，而不會讓她太暈（超過袋子上的「重量」限制）。

所以，現在你想選擇她眼睛打開/關閉的哪個部位（無論物品是否在麻袋中）。所以一個簡單的想法是選擇兩個選項中的最大值。如果她可以保持睜大眼睛不超過門檻，或只是閉着眼睛。但現在問題發生了變化，你看她是否睜着眼睛，她的眩暈閾值會降低（更容易解決分問題）。

使用此信息可以很容易地將揹包解決方案適應該問題，而無需使用回溯或遞歸。

這個想法是將所有先前解決的子問題保存在矩陣中，以便您可以重複使用結果而不是每次重新計算它們。注意你可以使用的一個技巧是你只需要矩陣的當前行和以前解決的問題，因爲揹包的遞推關係只需要那些條目:)

PS我是在給出這個問題的區域，解決它，很高興再次看到這個問題

來源

2012-02-15 20:34:13

應該挑有趣的選項，除非它會把貝西在病門檻。是否有更好的方法來做臨屋區T'

問題是，你沒有最大限度地發揮這裏的樂趣，你只是防止貝西生病。當你看到一段會讓她超過頭暈的限制時，你可以通過回溯並在前面的章節中選擇不好玩的選項來增加更多樂趣。假設你有輸入這樣，F中d順序：

而且，讓我們說，她已經接近極限頭暈時，她打上面的第一部分。你可以在前兩節採取有趣的選擇，並獲得6的F增加和850的D增加。也許這會讓她的權利在極限。現在你別無選擇，只能爲後面的部分採取不好玩的選擇。另一方面，如果您對前兩部分採取不好玩的選項，您可以在接下來的三部分中選擇有趣的選項，並在D增加到500時獲得48的F增加。

您的如果F：D比率大於1並且您有足夠的頭暈容量，則當前算法會採用有趣的選項。這是合理的，但不是最佳的。很可能沒有固定的比例會給出最佳的解決方案。相反，您需要考慮每個部分的每個選項的收益和成本。

來源

2012-02-15 20:31:28 Caleb

確定最大樂趣的算法

回答

相關問題