algorithm - 価格の比較方法

Question

購入したい商品のリストを作成します。それらすべてに一意の参照コードが与えられているとしましょう。購入できるサプライヤーのリストがあり、便宜上、各サプライヤーは各製品に同じ参照コードを使用しています。

一部のサプライヤーは送料を請求します。他の人は、あなたが一定額以下を費やす場合にのみ送料を請求します. 一部のサプライヤーは、複数回購入すると特定の製品を割引しますが、制限がある場合があります (1 つにつき 1 つ無料など)。

購入したい製品のリストを取得し、各サプライヤーからそれらすべてを購入する場合の合計費用を集計するのは非常に簡単です。私がやりたいのは、注文を分割した方が良いかどうかを判断するスクリプトを作成することです。

例えば：

小売業者 A の請求:
製品 A - £5
製品 B - £10
製品 C - £10
製品 D - £10
配送料 - £5

小売業者 B の請求:
製品 A - £5
製品 B - £12
製品 C - £12
製品 D - £30
送料 - £5 - £20 以上の買い物の場合は無料

この場合、商品 C だけを購入したい場合、最も安いのは小売業者 A です。

購入したい場合:
製品 Aを 1 つ
製品 Bを 2 つ
製品 D を 1 つ

最も安いのは、商品 A と B の小売業者 B (送料無料のため) であり、注文を分割して、小売業者 A から商品 D を購入します (配送料を含めても価格が大幅に低くなるため)。

ですから、私の頭の中では複雑な作業ではなく、紙の上では非常に簡単に解決できます。問題は、これをどのようにコードに変換するかです。私はそれを行うためのコードを探しているわけではありません - それを実装する方法の理論に関するいくつかのガイダンスです。

Answer 1

問題を単に各製品を購入するベンダーを選択することに限定し、ベンダーに依存する金額を費やすと、ベンダーに依存する送料の削減が得られる場合、問題を整数線形プログラム (IP またはこれは、実際に ILP を迅速に解こうとする多くの研究やソフトウェア パッケージが開発されているため、NP 困難であると疑われる問題に対する優れた戦略です。線形計画法と ILP についてオンラインで読むことができます。ILP 問題インスタンスには、変数、変数に対する線形制約、最小化または最大化する線形目的があります。問題に合わせて設定されたILPは次のとおりです。

ベンダーが販売する製品ごとに、ベンダーから購入する製品の数を示すベンダー製品変数が 1 つあります。これらの変数のそれぞれについて、変数が >= 0 でなければならないという制約があります。購入したい製品ごとに、その製品のすべてのベンダー製品変数の合計が、あなたが購入したい製品。

次に、配送割引を提供するベンダーごとに、割引を受けない場合は 0、割引を受けた場合は 1 になる配送割引変数があります。これらの配送割引変数のそれぞれについて、変数が >=0 かつ <= 1 でなければならないという制約があります。また、ベンダーの各ベンダー製品変数をその製品のベンダーの価格で乗算し、ベンダーのすべてを合計すると (ベンダーで費やしている合計金額が得られる)、これを示す制約もあります。 amount >= ベンダーの配送割引変数に、割引を受けるために必要なベンダーの最小金額を掛けたもの。

また、各ベンダーには、そのベンダーを使用する場合は 1、使用しない場合は 0 のベンダー変数があります。これらのベンダー変数 A のそれぞれについて、制約 1 >= A > =0 があり、ベンダーの各ベンダー製品変数 B についても、制約 A >= B/N があります。ここで、N はアイテムの総数です。買いたいでしょう。

最後に、最大化する目標は、各ベンダー製品変数にその製品のベンダーの価格を掛けて、すべてを合計し (目標 X のこの部分と呼びます)、各ベンダーの配送割引変数に送料を掛けることによって作成されます。割引を受けた場合に得られる削減額をすべて合計し (目標 Y のこの部分と呼びます)、各ベンダー変数にベンダーの割引前の送料を掛けて、すべてを合計し (目標 Z のこの部分と呼びます)、次にあなたの目的は単純に X - Y + Z を最小化することです。ILP を定義するために必要なのはこれだけです。それを ILP ソルバーに入力して、うまくいけばすぐに解を得ることができます。