私は私を悩ませている組み合わせの問題を抱えています。誰かに彼らの考えを教えてもらい、私が見落としているかもしれない明らかな解決策が欠けているかどうかを指摘してもらいたい。
1つのサプライヤからすべての供給品を購入するショップがあるとします。サプライヤーは販売アイテムのリストを持っています。各アイテムには次の属性があります。
size, cost, quantity, m, b
mおよびbは、次の式の定数です。
sales = m * (price) + b
この線は下向きに傾斜しています。この方程式は、特定の価格を請求した場合に販売できるアイテムの数を示しています。各アイテムには、独自のm値とb値があります。
その店の保管スペースと資金が限られているとしましょう。このショップは、倉庫を可能な限り最も収益性の高いアイテムで埋めたいと考えています。
（ちなみに、利益密度=利益/サイズ。利益密度はアイテムのサイズのみであると定義しています。サイズとコストの密度で作業できますが、そのためには必要があります。倉庫スペースのコストを知っています。それは私が現在知っている数ではないので、サイズを使用するだけです。）
アイテムの利益密度は、購入するほど低下します（以下を参照）。
一次方程式を反転すると、特定の期間に特定の量のアイテムを販売するために請求する必要のある価格がわかります。
price = (sales-b)/m
したがって、n個のアイテムを購入し、それらすべてを販売したい場合は、課金する必要があります。
price = (n-b)/m
これからの収入は
price*n = n*(n-b)/m
利益は
price*n-n*cost = n*(n-b)/m - n*cost
そして利益密度は
(n*(n-b)/m - n*cost)/(n*size)
または、同等に
((n-b)/m - cost)/size
したがって、利用可能なすべてのアイテムと、各アイテムの利益密度を含むテーブルがあるとします。
問題は、ショップが稼ぐ金額を最大化するために、各アイテムをいくつ購入するかということです。
1つの可能性は、コストとスペースの範囲内でアイテムの可能なすべての組み合わせを生成し、最も収益性の高いコンボを選択することです。1000アイテムのリストでは、これには時間がかかりすぎます。（私はこれを試しましたが、1000のリストには17秒かかりました。恐ろしいです。）
私が（紙の上で）試したもう1つのオプションは、リストの上位2つの最も収益性の高いアイテムを選択することでした。最も収益性の高いアイテムA、2番目に収益性の高いアイテムB、3番目に収益性の高いアイテムCと呼びましょう。アイテムBよりも収益性が低くなるまで、できるだけ多くのアイテムAを購入します。次に、Bを使用してこのプロセスを繰り返します。およびC、リスト内のすべてのアイテム。
ただし、アイテムBを購入した後、アイテムAがCよりも最も収益性の高いアイテムである場合があります。したがって、リソースが使い果たされるまで、現在の最も収益性の高いアイテムから次のアイテムに移動する必要があります。私はこれを行うことができましたが、それを行うには醜い方法のようです。
動的計画法を考えましたが、購入量によって商品の利益密度が変化するため、解決策が思いつきませんでした。
私は多重線形回帰を検討しましたが、「検討する」とは、「多重線形回帰はオプションですか？」と自分に言い聞かせたことを意味します。そしてそれで何もしませんでした。
私のスパイダーマンは、私を正面から見つめるはるかに明白な方法があることを私に教えてくれますが、私はそれを見ていません。私が自分自身とfacepalmを同時に蹴るのを手伝ってください。
これを動的計画法の演習として扱い、限られたリソースを最大限に活用することができます。
簡単な例として、スペースの制約を満たし、コストの制約を無視することを検討してください。次に、利用可能なスペースで最大の利益を生み出すアイテムを見つけたいと思います。使用されるスペースを整数として表現することが合理的であるように単位を選択し、次に、i = 1からアイテムの数まで、制限までのスペースの整数値ごとに、最初のiアイテムの選択を計算します。ほとんどの場合、その量のスペースが返されます。いつものように、iの回答からi + 1の回答を計算できます。0からスペースの制限までの各値について、そのスペースの量までのi +1番目のアイテムのすべての可能な数量を考慮して作業します。その量のアイテムを使用し、最初のiアイテムについてすでに計算した回答に従って、残りのスペースを使用することによる合計収益を計算します。
スペースとコストの両方に制約がある場合、動的プログラムの状態は単一の変数（スペース）ではなく、変数のペア（スペース、コスト）になりますが、作業量は増えますが、それでも解決できます。（0、0）から実際の制約までの（スペース、コスト）のすべての可能な値を考慮してください-0から最大スペースまでの単一の値のセットの代わりに、計算するリターンの2次元テーブルがあります。ただし、i = 1からNまで作業して、（スペース、コスト）の各制限について最初のiアイテムの可能な限り高いリターンを計算し、iの回答を使用してi +1の回答を計算することができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加