确定最大乐趣的算法

问题本身可以找到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

确定最大乐趣的算法

回答

相关问题