これは宿題に関する質問ではありません。これはオンライン製品を構築する際に直面している問題です。これが一般的なアルゴリズムの問題であるかどうか誰かが私に教えてくれることを望みます。価格に基づくホテル客室の最適配分
私は4つの部屋の設定があるとします。
第一ルーム - 2人 - 800
2STルーム - 3人 - 1400
第三ルーム - 2人 - 1000年
第四ルーム - 2人 - 2000
私は最低限の費用で4人を合わせたいとします。 そして、理想的には私は私が価格/人を使ってそれを解決しようとした
第一部屋+ 3番目の部屋を取得する必要がありますが、それは
が権利アルゴリズムを教えてください第一室と第二室の出力を与えることになるので、それは失敗しますこの問題を解決する
リチャードがコメントに正しく述べたように、これはナップザックに似ています。ただし、pseudo-polynomial dynamic programming solution from itを適用するのは非常に簡単です。
n部屋とm人がいるとします。 Pに初期化要素と長さをM + 1個のベクターCを作成する[I] = ∞ I> 0ため、及びP [0] = 0。 i番目のエントリがCであり、少なくともi人を保持できる最良のオプションがあります。各部屋の上に
ループ：
は今、トリプルループを実行します。現在考慮されている部屋は、pの人がcの人数を収容できるとします。各について
I = 0、...、Mのそれぞれjについて
= iは、...、分（mは、iが+ P）
チェックP [m]は最高のソリューションのコストのために。ここでは、すべての数学のコストが一定である仮定の下で
、これは複雑Θ（N M ）を持っています。
総費用だけでなく、最適な部屋の集合を見つけることは基本的に同じです。このベクトルには、エントリを更新した最後のルームと、このエントリを更新した最後のエントリの2つの追加エントリを追加します。
さらにそれを取り上げると、今は固定数の部屋があるとします。これは、部屋の条件の数が満たされている限り、高い価格を意味する可能性があります – nandonachi
ボックスパッキングや[ナップザック問題]（https://en.wikipedia.org/wiki/Knapsack_problem）のようなサウンドです。あなたが多項式時間にそれを行うことができれば、100万ドルの賞金があります。実際のシステムは完全なソリューションを探すのではなく、ヒューリスティックを適用して十分な解決策を得る。 – Richard
一部の実際のシステムでは実際に実際の最適化を使用して実際の最適解を得ています。 –