0

合計 = 1 の理想的な比率のセットがあるとします。たとえば、

set = [0.2, 0.1, 0.4, 0.3]

しかし、値が 0 に等しくない場合、値を下回ってはならないという規則があるとします。

min = 0.25

直感的には、次のように適合すると言えます。

set = [0.25, 0, 0.425, 0.325]

しかし、私はそこで何をしたのかよくわかりません。

この種の問題に名前はありますか？一般解とは？

4

3 に答える 3

1

アルゴリズム

これはおおよそあなたが提案しているアルゴリズムだと思います(Pythonで):

def fx(arr, m): 
  arr.sort()
  if arr[0] >= m:
    return arr 

  return _fx(arr, m, 0)

def _fx(arr, m, i): 
  extra = arr[i]
  arr[i] = 0 

  for j in range(i + 1, len(arr)):
    if arr[j] >= m:
      break
    extra -= m - arr[j]
    arr[j] = m 
    if extra < 0:
      arr[j] += extra
      return _fx(arr, m, i + 1)

  numToBump = len(arr) - j 
  for k in range(j, len(arr)):
    arr[k] += extra / numToBump

  return arr

説明：

まず、配列をソートします。最初の要素が最小値を超えていれば、完了です。それ以外の場合は、ヘルパー メソッド ( _fx) を引数とゼロ アウトするインデックス( ) で呼び出します0。

ヘルパー メソッドでは、i要素 th をゼロにして、その元の値を、分配する必要がある「余分な」量として保存します。まず、 from を取得して、最小値よりも小さいすべての要素を最小値にバンプしようとしextraます。終了する前に余分なものがなくなった場合は、次の要素をゼロにしようとします。

すべてが最小値を超えている場合は、まだ触れていない要素間で残りの余分な部分を分割します。

注: 要素を別の順序で返していますが、最後に並べ替えを解除するのは非常に簡単です。

例

これらはすべて のしきい値を使用してい0.25ます。

[0.1, 0.2, 0.3, 0.4] -> [0, 0.25, 0.325, 0.425]

[0.1, 0.1, 0.4, 0.4] -> [0, 0, 0.5, 0.5]
于 2013-08-07T20:18:48.867 に答える
1

この最小値を とするとm、一般的な解決策は次のようになります。

while there is a none zero value smaller then `m`:
   x <- lowest value
   for each y != x:
      y += y*x/ (1-x)
   x <- 0

上記のループが各反復で sum==1 を保持していることは簡単にわかります。理由は次のとおりです。

x を除くすべての要素の合計 = 1-x
したがって、すべての増加の合計は

 x/(1-x) * [sum of all elements excluding x] = x / (1-x) * (1-x) = x

そのため、各反復で総和が同じ値だけ増減されたため、総和は 1 のままでした。

于 2013-08-07T18:26:13.873 に答える
0

少なくとも私が正しく理解していれば、最小のものを取り、それが最小値よりも小さい場合はゼロに減らします。次に、最小値を満たすのに十分な量を (十分にある場合) 次に小さいものに与えます。(十分でない場合は、次に小さいものをゼロにし、その値を配布するものに追加して、繰り返します)。

最小から最小までがあり、残りの部分に分配するものが残っている場合は、合計を取得するために他の部分を合計することから始めます。次に、他の数値を調べて、各数値を合計で割って比率を求めます。次に、それぞれに行く量は、分配する必要のある量を乗じた比率です。

たとえば、元の数値では次のようになります。

set = [0.2, 0.1, 0.4, 0.3]

2 番目の項目をゼロにし、最初の項目に .05 を与えて、.05 を配布用に残します。

次に、他の 2 つを追加して 0.7 を取得します。他のそれぞれをそれで割り、比率を取得します: 0.4/0.7 および 0.3/0.7。次に、これらの各比率に 0.05 を掛けて、それぞれに分配する金額を取得します: 4/7*.05 = .0285714... および 3/7*.05 = .0214857...

そのため、それぞれにそれだけの量を追加します。最後の 1 つに到達すると、残っているものをすべて追加するだけなので、丸めエラーがあった場合、合計は最初の値のままになります。

于 2013-08-08T04:54:54.487 に答える