4

php5.2とMySQL4.1.22の使用

私は、最初は単純に見えたが、それ以来、単純でクリーンな解決策に関して私を回避してきた何かに出くわしました。

製品の「パッケージ」が事前に定義されています。パッケージ1には、製品A、B、およびCが含まれている場合があります。パッケージ2には、A、C、D、Gなどが含まれている場合があります。パッケージのサイズは3〜5製品です。

これで、顧客は利用可能な10個の製品を選択して、「カスタム」パッケージを作成できます。すでに特定の事前定義されたパッケージがあるので、可能な場合は（出荷を容易にするために）既存のより小さなパッケージを使用してカスタムパッケージを構築したいと思います。

したがって、たとえば、顧客は製品A、B、C、D、E、およびFの「カスタムパッケージ」を作成することを選択します。Fooと呼ばれるA、B、およびCを含む事前定義されたパッケージがすでにあります。したがって、順序はFoo、D、E、およびFになります。

キャッチは、個々のアイテムの量が最も少なく、次にパッケージの量が最も少ないことです。例えば：

カスタムパッケージ：A、B、C、D、E、F、G、H、I、J。

事前定義されたパッケージ（1）：A、B、C、D、E

事前定義されたパッケージ（2）：A、B、C

事前定義されたパッケージ（3）：D、E、F

単純に最大の一致を取る場合、1つの（5pc）パッケージと5つの個別のアイテムがあります。パッケージ（2）も（3）も残りのアイテムで構築することはできません。

もっと深く見てみると、パッケージ（1）をビルドしないことで、代わりにパッケージ（2）とパッケージ（3）をビルドできることがわかります。つまり、2つのパッケージと4つの個別のアイテムがあります（このビジネスルールではより適切な選択です）。

私はMySQLを使用しているので、（私の知る限り）サブセレクトの1つのレイヤーしか使用できないという制約を受けています。したがって、このソートはphpで実行する必要があります。array_intersect（）を使用して一致を判別することを検討しましたが、事前定義されたパッケージの数が直線的に増加するにつれて、処理に関して私が見つけたすべての方法が指数関数的に増加します。

私はこれを他の数人のコーダーの友人によって実行しましたが、簡単な答えがあるはずですが、私たち全員が思ったほど単純ではないことがわかりました。なので、ここに素敵なヌードルストレッチャーとして投稿しようと思いました。よろしくお願いします！

4

3 に答える 3

4

この問題は一般的に「難しい」問題です (計算の複雑さの観点から言えば)。実際、ナップザック問題のような古典的なアルゴリズムの問​​題の 1 つに還元される可能性が高いと頭の後ろでいくつかの鐘を鳴らしますが、適切な名前を付けることができません。

ただし、このような小さな問題スペース (10 個の製品しか選択できません) では、力ずくで物事を解決するのはかなり迅速なはずです。誰かがカスタム ビルドを提出したら、すべての可能性を再帰的に攻撃し、どれが最適かを確認します。

つまり、彼らが選択したコンポーネントを取得し、最初に「パッケージ 1」のコンポーネントをそこから削除しようとします。可能であれば、残りのコンポーネントを取り出して、そこから「パッケージ 2」のコンポーネントを取り出すようにしてください。これまでに見つけた最適なソリューションを追跡してください。

それでも十分に高速でない場合 (ビルド済みパッケージの数によっては、おそらくそうなると思います)、動的プログラミング手法を適用して高速化できます。

追加するために編集：

可能性の数と実際に実行するのにかかる時間によっては、上記のコードを記述してから、考えられるすべての組み合わせのすべてのソリューションを事前に計算することをお勧めします。その後、誰かがカスタム ビルドを送信すると、毎回ゼロから計算するのではなく、回答を取得するだけで済みます。

それらすべてを事前に計算したくない場合でも、誰かがカスタム ビルドを実行するたびに結果を保存することをお勧めします。その後、他の誰かが同じカスタム ビルドを実行した場合でも、ソリューションを再計算する必要はありません。 .

于 2009-04-09T22:14:23.193 に答える
0

問題をもう少し複雑にしてすみません。:-)

考えられる解決策を事前に計算したり、事前に定義されたパッケージから実際に消費者に選択してもらいたいと思うかもしれませんが、事前に定義されたパッケージの在庫がなくなったらどうなるでしょうか?

現時点で注文を完了するための解決策がない場合はどうなりますか? その後、注文の一部を発送しますか?もしそうなら、後で事前に定義されたパッケージを選択できることがわかっていても、単一の商品を含めますか?

そして、事前定義されたパッケージに「設定」が割り当てられていないことを本当に確信していますか? 「ABCD」と「ABC」および「BCD」の注文時に選択する定義済みパッケージのように、定義済みパッケージは存在しますか? たとえば、事前定義されたパッケージ「ABC」が頻繁に在庫切れであることがわかっている場合、可能な限り「BCD」が優先される可能性があります。

したがって、自動化されたソリューションを見つけようとするのではなく、ハードコードされたルールを簡単に変更できるモデリングを使用する必要があるかもしれません。もちろん、これは PHP 自体である可能性もあります。

于 2009-04-09T23:42:12.093 に答える
0

お客様に手伝ってもらうことをお勧めします。製品選択画面で、どのパッケージ セットが利用可能かを示し、それらを組み合わせてもらいます (着ぐるみの合計が特別な取り扱いをカバーするのに十分であるように、適切な価格設定を行います)。

于 2009-04-09T22:07:15.067 に答える