これが多項式時間で実行できるかどうかさえわかりません。
問題：
実数の 2 つの配列が与えられると、
A = (a[1], a[2], ..., a[n]), B = (b[1], b[2], ..., b[n]), (b[j] > 0, j = 1, 2, ..., n)および数値、 のサブセットを
k見つけます。このサブセットには、が最大化されているような要素が正確に含まれています。ここで、 .A'A (A' = (a[i(1)], a[i(2)], ..., a[i(k)]))k(sum a[i(j)])/(sum b[i(j)])j = 1, 2, ..., k
たとえばk == 3、 と{a[1], a[5], a[7]}が結果の場合、
(a[1] + a[5] + a[7])/(b[1] + b[5] + b[7])
他のどの組み合わせよりも大きくする必要があります。どんな手掛かり？
のエントリが正であると仮定するとB(この特殊なケースが役立つように思えます)、O(n^2 log n)アルゴリズムがあります。
t最初に、特定の について、次のような解が存在するかどうかを判断する問題を解決しましょう。
(sum a[i(j)])/(sum b[i(j)]) >= t.
分母をクリアすると、この条件は
sum (a[i(j)] - t*b[i(j)]) >= 0.
kの最大値を選択するだけですa[i(j)] - t*b[i(j)]。
tさて、が未知の場合の問題を解決するために、動的アルゴリズムを使用します。t時間変数であると考えてください。n私たちは、粒子が初期位置Aと速度を持つ1 次元物理システムの進化に関心があり-Bます。各粒子が他の粒子と交差するのは最大 1 回なので、イベントの数は ですO(n^2)。交差間ではsum (a[i(j)] - t*b[i(j)])、 の同じサブセットが最適であるため、 の最適値は線形に変化しkます。
B に負の数を含めることができる場合、これは NP 困難です。
この問題の NP 硬度のため:
k と配列 B が与えられた場合、合計がゼロになる B のサイズ k のサブセットがあります。
その場合、A は重要ではなくなります。
もちろん、あなたのコメントから、 B には正の数が含まれている必要があるようです。