最大の楽しみを決めるアルゴリズム

Question

問題自体はhereで見つけることができます。それの要点は、ベッシーがジェットコースターに乗っていることですが、めまいになります。彼女が "めまいの限界"を越えなければならない楽しみの最​​大量はいくらですか？ K（500≤1≤K）量である。

N（千≤1≤N）は、この特定のジェットコースターのセクションの数である

が

"NKL： 入力から成り（1≦L≦300,000）は、Bessieが許容できる眩暈の限界です。もし彼女のめまいがLよりも大きくなると、Bessieは

次のN行にはそれぞれ2つの整数があります：

FD F（1≤F≤20）が、彼女はそのセクションに彼女の目が開いたままならば入手シェルBessies総楽しみに増加しており、D（500≤1≤D）が増加することである

彼女が目を覚ましていれば、彼女はめまいのレベルになります。セクションが順番に表示されます「

これを解決するために私のアルゴリズムは次のようになります。

 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; 
      } 

しかし、これはは常には正しい結果が得られない問題である何それは選ぶべきです。？それは病気のしきい値を超えベッシーを入れない限り楽しいオプション、。それを行うには良い方法はありますか？それは 病気しきい値を超えベッシーを入れない限り

Answer 1

ここでは、コードを渡すのではなく、問題の解決方法を説明しています。

基本的なアプローチは、動的プログラミングを使用して解決することです。これは、Knapsack problemと呼ばれるものになります。このように考えると、彼女のめまいは、彼女が一度に袋にどれくらい持ち歩くことができるかということであり、楽しみは彼女が最大にしたいものです（彼女が袋で運ぶ「アイテム」の価値と比べて）。今私たちがやりたいことは、彼女をあまりにもめまいにすることなく（袋の "体重"限界を超えて）ローラーコースターから最大の喜びを得ることです。

これで、目を開閉している部分（袋に入っているかどうか）を選択します。したがって、これを考える簡単な方法は、両方のオプションの最大値を選択することです。閾値を超えずに目を開いたままにしたり、目を閉じたままにしておくことができるかどうか。しかし、今問題が変わると、目を開いたままにしておくと、めまいの閾値が下がります（問題の解決が容易になります）。

この情報を使用すると、バックトラッキングまたは再帰を使用せずにこの問題にナップザックソリューションを適合させることが容易になります。

考え方は、以前に解決したすべての部分問題を行列に保存して、毎回再計算する代わりに結果を再利用できるようにすることです。あなたが使用できるトリックは、ナップザックの反復関係にはこれらのエントリしか必要でないため、行列の現在の行と前に解いたものだけが必要であることに注意してください。

PSこの問題は、それを解決しました。この問題をもう一度見てうれしく思います。

Answer 2

それは、楽しいオプションを選択する必要がありますが。ですがそれをするより良い方法t？

問題は、あなたがここでの楽しみを最大限にしていないということです。ただ、ベッシーが病気にならないようにするだけです。めまいの限界を超えてしまうようなセクションになると、前のセクションでは楽しいオプションをバックトラッキングして追加することで、もっと楽しい時間を追加できます。あなたがF Dの順に、次のように入力を持っていると言う：

さらに

1 400 
5 450 
10 25 
18 75 
20 400 

、のは、彼女は上記の最初の部分に当たったとき、彼女はすでに限界に近いめまいだとしましょう。あなたは、最初の2つのセクションで楽しいオプションを取って、6のF増加と850のD増加を得ることができます。それは彼女が限界に来るかもしれません。今度は、その後のセクションで楽しい選択肢を取ること以外に選択肢はありません。一方、最初の2つのセクションで楽しくないオプションを選択した場合は、次の3つのオプションを選択してFの値を48にしてDを500増加させるだけです。

現在のアルゴリズムは、F：D比が1より大きく、十分なめまい能力が残っている場合には、楽しい選択肢を取ります。それは合理的ですが、最適ではありません。固定比率は最適な解決策を提供しない可能性があります。代わりに、各セクションの各オプションの利点とコストを考慮する必要があります。