6

この問題を効率的に解決する方法を見つけようとして非常に苦労しています。それがどのように進むかを説明しましょう：

「働き者のお母さんは、3 人の子供、アメリア、ジェシカ、ブルーノのために、栄養価の異なる果物をいくつか購入しました。女の子は 2 人とも太りすぎで、非常に凶暴で、かわいそうなブルー​​ノにはいつも何も残らないので、母親は食べ物を分け合うことにしました。次の方法：

  • アメリアは最も重いものであり、栄養価が最も高くなります
  • ジェシカはアメリアと同じかそれ以下の金額を手に入れる
  • ブルーノはジェシカと同等かそれ以下の量を摂取していますが、ルール ( A >= J >= B ) を尊重しながら、彼に可能な限り高い栄養価を与える方法を見つける必要があります。」

注: 元の問題は別の方法で説明されていますが、考え方は同じです。クラスメートが Google でヘルプを求めたときに、この投稿を見つけてほしくありません。

私の先生から与えられたテストケースの1つは次のとおりです。

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 番目のアイデアは、動的計画法を使用することです。列ヘッダーには果物のリストの位置があり、行ヘッダーには同じです。文字で説明するのは難しいので、前の例の表を先に進めます { 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 をもう一度チェックしようとします。それがテーブルにある場合は、それを選択します。その後、それぞれのポジションを使用済みとしてマークし、未使用のポジションを合計してブルーノの成果を取得します。

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

うわー、こんなにたくさん xX を入力したことに気がつきませんでした。博士。ヘルプ/ガイドをいただければ幸いです:D

編集:誰かが試してみたい場合に備えて、テーブルを生成するコードを作成しました。

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();
        }

    }
4

2 に答える 2

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);
    }

これは、比較的類似した値の果物に対して機能します。他のすべての果物を組み合わせたものよりも価値の高い果物を追加すると（私は偶然に一度行ったことがあります）、少し壊れます。

于 2012-07-01T09:53:24.820 に答える
1

少し計算量が多い方法は、アメリアの栄養価が最も高いものから始めて、ラウンドロビン方式で果物を割り当てることです。
そこから、アメリアが持っている最も栄養価の低い果物から段階的にループし、(a) 果物をジェシカに与えるか、(b) ルールを満たしながら、果物をジェシカが持っている果物と交換する、のいずれかの組み合わせを試します。次に、同じ方法をジェシカとブルーノに適用します。スワップまたはギブができなくなるまで、これらの 2 つのループを繰り返します。
jess/bruno に同時にギブ/スワップすることは、少しトリッキーですが、より高速になる可能性があります。A が保持する 2 個の果物ごとに、4 つのオプションを試すことができます。同時に J と B のバランスを取ろうとすると、さらに多くのオプションを試すことができます。

より高速なアルゴリズムについては、数学スタック交換サイトで質問してみてください。これは非常に集合論の問題です。

于 2012-07-02T00:28:59.290 に答える