0

私は魔法のカードを「最適に」購入するためのプログラムに取り組んでいます。このサイトには、各ユーザーが「ミニショップ」を持っています。オークションのない eBay を考えてみてください。

ユーザーが購入したいカードのリストを入力すると、サイトからすべてのオファーを取得して、「最適な」ショッピング リストを出力します。最適な意味の最も安い. 価格はお店によって異なり、カードを購入する枚数によって送料も変わります。

そのリストを作成するアルゴリズムを実装したいと思います。私は(私が思うに)動作するものを書きましたが、それがどれほどうまく機能するかわかりません。

だから私の質問はこれです: この問題は既存のアルゴリズムで解決できますか? カードごとに最大 1000 のオファーを処理する必要があります (通常は 40 ~ 60 枚のカードなので、約 50,000 の異なるオファー)。

誰かがこれについて正しい方向に私を向けることができますか?

4

1 に答える 1

3

「パーティション」または「ビンパッキング」の問題 (どちらもやりたいことにマッピング可能) は、NP 完全であることが知られています。したがって、最適なソリューションを確実に得る唯一の方法は、考えられるすべてのソリューションを試して、最適な方法を選択することです。ユーザーが 1,000 枚のカードを購入したい場合、考えられるすべてのオプションを試すことは計算上不可能であるため、ヒューリスティックを使用する必要があります。

于 2013-09-20T20:09:30.457 に答える