最適な出力のために所定のリソース（例えば予算）を配布する最良の方法

Question

与えられたリソース（例えば、予算）が、提供されたリソース上で異なる結果をもたらす異なるオプションに最もよく分散される解決策を見出そうとしています。 。

私はN = 1200といくつかの機能を持っているとしましょう。 （a、b、c、dはいくつかの未知の変数です）

f1(x) = a * x 
f2(x) = b * x^c 
f3(x) = a*x + b*x^2 + c*x^3 
f4(x) = d^x 
f5(x) = log x^d 
... 

そしてまた、のは、その入力xに基づいて、異なる結果が得られ、これらの機能の存在n数、mが一定であるx = 0 or x >= m、としましょう。

私は与えられた関数の正確な公式を見つけることができませんが、私は出力を見つけることができます。これは私が行うことができますことを意味します

X = f1(N1) + f2(N2) + f3(N3) + ... + fn(Nn)がNnに番号を配布する方法があり、Xが最大である特定のケースを見つけるとどこ(N1 + ... Nn) = N何度でも。

現在、利用可能なライブラリを使用して、計算力が最も低いNのベストディストリビューションを実際に見つける方法を教えてください。

Answer 1

整数に制限された割り当てに満足すれば、コストO（Nn）の動的プログラミングソリューションがあります。スケーリングによって精度を上げることができますが、これによってCPU時間が増えます。

各i = 1〜nについて、要素jが最初のi関数のみを使用して最大の歩留まりを与える配列を維持し、jの合計余裕を与えます。

i = 1の場合、これは単にf1（）の結果です。

i = k + 1の場合、jの結果を計算するときは、f_ {k + 1}（）と最初のディストリビューションからの最良のリターンを示すテーブルk関数を作成します。したがって、kに対して作成されたテーブルを使用して、i = k + 1のテーブルを計算することができます。

最後に、n個の関数とN個のリソースに対して最良のリターンを得ます。 iとkのすべての可能な値に対して、最初のi関数の中にk個の単位を分散させる最善の方法を指示する配列のセットを維持すると、最良の答えが何であるかを簡単に見つけることができます。次に、f100（）の最適な割り当てを調べて、Nからf100（）に割り当てられた値を減算し、得られたリソースを考慮してf99（）の最適な割り当てを調べ、すべてのf（）の最適な割り当て。 f1（x）= 2x、f2（x）= x^2、x> 0の場合はf3（x）= 3、それ以外の場合は0と仮定します。 3つのリソースがあるとします。

第1のテーブルは、f1（x）であり、0,1,2,3単位に対して0,2,4,6である。

2番目の表は、0,1,2,3単位に対してf1（x）とf2（x）を使用して実行できる最善のもので、0,2,4,9、x = 2。

3番目の表は0,3,5,9です。f3（）には1単位を使用し、2番目の表には最良の解決策として残りの3と5を得ることができます。 9は、2番目の表の中で最良の解です。f（3）

ここでは9が最良の答えです。そこに到達する方法を理解する1つの方法は、テーブルを保持し、その答えを再計算することです。 9は2番目のテーブルからのf3（0）+ 9から来るので、3つのユニットすべてがf2（）+ f1（）に使用可能です。第2のテーブル9はf2（3）から来て、f（1）のための単位がなく、f1（0）+ f2（3）+ f3（0）を得る。

ご段階で使用するリソースを作業しているとき、私= K + 1あなたは私は= Kあなたがでいくつかを使用することを決定した後、あなたが余っているリソースから期待して正確に結果を説明しますテーブル形式を持っています段階i = k + 1である。最良の分布は、ステージi = kの残りのリソースの可能なすべての数が与えられたときの最良の分布について結果を計算したので正しくない。