Shareフルーツ（フェアリー）（動的プログラミング）

Question

この問題を効率的に解決する方法を見つけるのは非常に困難です。

"勤勉なお母さんは、3人の子供、アメリア、ジェシカ、ブルーノの栄養価が異なるいくつかの果物を購入しました。どちらの女の子も太りすぎで、非常に悪質で、常に貧弱なブルーノを残しています。何もない、彼らの母親は次のように食べ物を共有することを決めたので：アメリアは最も重い1であることが

栄養価のほとんどの量ジェシカが等しいかアメリア

ブルーノが取得するよりも少ない量を取得し、取得

• ジェシカと等しいかそれより少ない金額ですが、あなたは彼に（A> = J> = B） "

注：元の問題は異なって説明されていますが、私のクラスメートがこの投稿を見つけるのは嫌です彼らはheheのためのGoogleのgoogle。

先生によって与えられたテストケースの

つ以下の通りです：

The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1} 

Input: 
7 -----> Number of Fruits 
4 2 1 8 11 5 1 ----> Fruits Nutritional Values 

Output: 
1 11 ----> One fruit, their nutritional values sum for Amelia 
5  ----> Position of the fruit in the list 
3 11 ----> Three fruits, their nutritional values sum for Jessica 
1 2 6 ----> Position of the fruits in the list 
3 10 ----> Three fruits, their nutritional values sum for Bruno 
3 4 7 ----> Position of the fruits in the list 

注：私はダイビングの方法はいくつかの子供たちの間で果物があることを承知していますが、それは本当にとして重要ではありません。それは規則A> = J> = Bに従う限り長いです。

最初に、すべての部分集合を生成し、それぞれがその合計と使用中の位置を持つアルゴリズムを作成しました。その方法は、果実のリストが50果実を持つことができ、サブセットアルゴリズムがO（2^n）であるため、すぐに破棄されました。私は記憶がなくなった。

私が持っている第2のアイデアは、動的プログラミングを使用することです。列ヘッダーでは、私はFruit's Listの位置を持っています。行ヘッダーも同じです。文字で説明するのは難しいですから、前の例のテーブルを先に進めます{4、2、1、8 、11,5,1}。

00 01 02 03 04 05 06 07 
00 
01 
02 
03 
04 
05 
06 
07 

我々は位置1,2,3、...、7

00 01 02 03 04 05 06 07 
00 00      <---No positions in use 
01 04      <---RowPosition 1 + Column Position(Column 0) (4+0) 
02 06      <---RowPosition 1 + RowPosition 2 + Column Position (4+2+0) 
03 07      <---RP(1) + RP(2) + RP(3) + CP(0) (4+2+1+0) 
04 15      <--- (4+2+1+8+0) 
05 26 
06 31 
07 32      <--- (4+2+1+8+11+5+1+0) 

を追加するの下に、我々は行に進むたびに今、あなたはそれが行く方法を知っていることを最初の行を追加することができます

00 01 02 03 04 05 06 07 
00 00 04 02 01 08 11 05 01 <-- Sum of RP + CP      
01 04 00 06 05 12 15 09 05 <-- Sum of RP(0..1) + CP      
02 06      
03 07      
04 15      
05 26 
06 31 
07 32      

第1位が既に使用されているため、00を付けます。完成したテーブルは次のようになります。

00 01 02 03 04 05 06 07 
00 00 04 02 01 08 11 05 01      
01 04 00 06 05 12 15 09 05       
02 06 00 00 07 14 17 11 07     
03 07 00 00 00 15 18 12 08     
04 15 00 00 00 00 26 20 16      
05 26 00 00 00 00 00 31 27 
06 31 00 00 00 00 00 00 32 
07 32 00 00 00 00 00 00 00  

これでわかりました。私は栄養価の合計を子供の量で割る32/3 = 10.6667、天井は11になります。私は11をチェックしようとします。それがテーブルにあればそれを選択し、行の位置をマークします。テーブルの列を使用している場合は、テーブルにある場合は11をもう一度チェックし、それ以外の場合は10、または9などを検索して見つけます。その後、私は使用されたそれぞれのポジションをマークし、未使用ポジションを合計してブルーノの果実を得ます。

私の方法で欠陥が見つかったため、これを行うにはより良い方法が必要であることがわかっています。表にはいくつかのサブセットの合計しかありません。だから、それはいくつかのテストケースでは有害になるかもしれません。たぶん3D Memoization Cube？と思うと、それはあまりにも多くのメモリを消費すると思うし、私も256MBも限界がある。

うわー、私はこの多くのx.Xを入力したことを認識しませんでした。私はたくさんのtlを取得しないことを願っています。ドクター。任意のヘルプ/ガイドは非常に高く評価される：D

EDIT：私はそれを試してみたい場合にテーブルを生成するコードを作った。

static void TableGen(int[] Fruits) 
    { 
     int n = Fruits.Length + 1; 
     int[,] memo = new int[n, n]; 

     for (int i = 1; i < n; i++) 
     { 
      memo[0, i] = Fruits[i - 1]; 
      memo[i, 0] = memo[i - 1, 0] + Fruits[i - 1]; 

      for (int j = i + 1; j < n; j++) 
       memo[i, j] = memo[i, 0] + Fruits[j - 1];    
     } 


     for (int i = 0; i < n; i++) 
     { 
      for (int j = 0; j < n; j++) 
       Console.Write("{0:00} ", memo[i, j]); 

      Console.WriteLine(); 
     } 

    } 

Answer 1

for(i = 0; i < count; i++) 
    { 
    currentFruit=Fruits.Max(); 

    if(Amelia.Sum() + currentFruit < Jessica.Sum() + currentFruit) 
     { 
     Amelia.Add(currentFruit); 
     Fruits.Remove(currentFruit); 
     continue; 
     } 
    if(Jessica.Sum() + currentFruit < Bruno.Sum() + currentFruit) 
     { 
     Jessica.Add(currentFruit); 
     Fruits.Remove(currentFruit); 
     continue; 
     } 
    Bruno.Add(currentFruit); 
    Fruits.Remove(currentFruit); 
    } 

これは比較的類似した値との果物のために動作します。あなたが他のすべての果物（それは私が一度偶然行った）よりも大きな値の果物を追加すると、それはちょっと壊れます。

Answer 2

若干計算量が多い方法は、アメリアの栄養価が最も高いものからラウンドロビン方式で果物を割り当てることです。
そこから、アメリアが保有する最も低い栄養価の果物を徐々にループし、（a）果物をジェシカに与えるか、（b）果実をジェシカが持つものと交換するか、ルール。 その後、jessicaとbrunoに同じメソッドを適用します。これらの2つのループを繰り返すことで、それ以上のスワップや付与ができなくなるまで繰り返します。
ややトリッキーですが、潜在的に速いのは、同時にjess/brunoに与える/スワップすることです。 Aが保持するフルーツ2個につき、4つの選択肢があります。同時に試してみると、さらに均等に試してみてください。

もっと速いアルゴリズムを試すには、数学のスタックこれは非常に多くの集合論的問題である。