1

さまざまな時間に分散させたいさまざまな数のアイテムがあります。私が抱えている問題は、「オーバーハング」の間のスペースができるだけ等しくなるように残りをどのように分配するかです。たとえば、5 時間にわたって 13 個のアイテム (X) がある場合、最終的には次のようになります。

Hours:    1    2    3    4    5
---------------------------------
          x    x    x    x    x
          x    x    x    x    x  
          x         x         x

私がこれを考えすぎているかどうかはわかりません。現在、アイテム数が時間数よりも多いかどうかを確認しています。そうであれば、（アイテム数/時間数）を割ります。では、（時間数/余り）を割る必要があると思いますが、上記の例では、5/3=1.6となり、2に丸められますMath.Floor。本当にどうやって。

5 時間で 4 アイテムの場合、最終的に X で終了したい 2 アイテムで Y で、1 アイテムで Z である

 1    2    3    4    5
------------------------
 x    x         x    x

      y         y

           z

項目数、時間数は変動制です。

わかりました、私は現在正しい軌道に乗っていると思います。現在、ビンを半分に分割し、残りの 1 つを中央のビンに入れようとしています。これを余りが 0 になるまで再帰的に繰り返します。

4

2 に答える 2

4

編集: 偶数時間とアイテムの問題を修正しました。

これは難しい問題であり、以下が解決策です。完全に一般的な問題の解決策を書いたので、任意の時間とアイテム数で機能します。出力例は次のとおりです。

Items=10, Hours=14
XX XX XX XX XX

Items=11, Hours=14
XX XXXXX XX XX

Items=12, Hours=14
XX XXXXXXXX XX

Items=16, Hours=13
XXXXXXXXXXXXX
     XXX

Items=17, Hours=13
XXXXXXXXXXXXX
X    X X    X

Items=18, Hours=13
XXXXXXXXXXXXX
X    XXX    X

Items=19, Hours=13
XXXXXXXXXXXXX
X X  X X  X X

Items=20, Hours=13
XXXXXXXXXXXXX
X X  XXX  X X

Items=21, Hours=13
XXXXXXXXXXXXX
X XX X X XX X

以下のソリューションの仕組みは次のとおりです。

  1. 塗りつぶされた行の数は、(アイテム/時間) * 時間で取得できる些細なことです。
  2. 最後の行は、すべての魔法が必要な場所です。
  3. 残りのアイテム数が奇数の場合、中央をオンにしたい。時間数も奇数の場合、中心は明確に定義されていますが、そうでない場合は運が悪く、その場合は「不均衡」が生じます。
  4. 偶数のアイテムについては、それらをペアにして、各ペアをバランスの取れたバイナリ ツリーの順序で配布します。これは基本的に、最初に各ペアを最後に置くことを意味します。次に、次のペアを途中で再帰的にパターンに従います。ここが一番分かりにくいところなので、紙とペンがおすすめです:)。

コードは次のとおりです。

static void Main(string[] args)
{
    var hours = 13;
    for (var items = 16; items < 22; items++)
        PrintDistribution(items, hours);
}

private static void PrintDistribution(int items, int hours)
{
    Console.WriteLine(string.Format("\nItems={0}, Hours={1}", items, hours));
    for (var i = 0; i < (items / hours) * hours; i++)
    {
        Console.Write('X');
        if ((i + 1) % hours == 0)
            Console.WriteLine();
    }

    var line = new StringBuilder(new string(' ', hours));
    var remaining = items % hours;
    var evens = remaining / 2;
    var odd = remaining - (evens * 2);
    var seq = BinaryTreeSequence(hours / 2).GetEnumerator();
    for (var i = 0; i < evens; i++)
    {
        seq.MoveNext();
        line[seq.Current] = 'X';
        line[hours - seq.Current - 1] = 'X';
    }

    if (odd > 0)
        if (hours % 2 == 0)
        {
            seq.MoveNext();
            line[seq.Current] = 'X';
        }
        else
            line[hours / 2] = 'X';

    Console.WriteLine(line);
}


public static IEnumerable<int> BinaryTreeSequence(int count)
{
    if (count > 1)
        yield return count - 1; 
    if (count > 0)
        yield return 0;

    var seqQueue = new Queue<Tuple<int, int, int>>();
    Enqueue(seqQueue, 0, count - 1);

    for (var seqIndex = count - 2; seqIndex > 0; seqIndex--)
    {
        var moreNeeded = seqQueue.Count < seqIndex;

        var seq = seqQueue.Dequeue();
        yield return seq.Item1;

        if (moreNeeded)
        {
            Enqueue(seqQueue, seq.Item1, seq.Item3);
            Enqueue(seqQueue, seq.Item2, seq.Item1);
        }
    }
}

private static void Enqueue(Queue<Tuple<int, int, int>> q, int min, int max)
{
    var midPoint = (min + max) / 2;
    if (midPoint != min && midPoint != max)
        q.Enqueue(Tuple.Create(midPoint, min, max));
}
于 2013-11-13T22:16:25.723 に答える
1

おおよその解決策は次のとおりです。ゼロベースのインデックスとアイテムを含むタプルを返します。（あなたxのようなダミー値だけでなく、アイテムが重要かもしれないと思いました）場合によっては最適な間隔を選択しませんが、常に近いと思います（つまり、ギャップは必要以上に大きくなりません） 、常に正しい数のアイテムを返します。

public static IEnumerable<Tuple<int, T>> SplitItems<T>(IEnumerable<T> items, int count)
{
    var itemList = items.ToList();
    int lastRowCount = itemList.Count % count;
    int wholeRowItemCount = itemList.Count - lastRowCount;

    // return full rows: 0 <= i < wholeRowCount * count
    for (int i = 0; i < wholeRowItemCount; i++)
    {
        yield return Tuple.Create(i % count, itemList[i]);
    }

    if (lastRowCount > 0)
    {
        //return final row: wholeRowCount * count <= i < itemList.Count
        double offset = (double)count / (lastRowCount + 1);
        for (double j = 0; j < lastRowCount; j++)
        {
            int thisIntPos = (int)Math.Round(j * count / (lastRowCount + 1) + offset, MidpointRounding.AwayFromZero);
            yield return Tuple.Create(thisIntPos, itemList[wholeRowItemCount + (int)j]);
        }
    }
}

使用方法の例として：

Console.WriteLine(string.Join("\r\n", SplitItems(Enumerable.Range(1, 12), 5)));
// prints
(0, 1)
(1, 2)
(2, 3)
(3, 4)
(4, 5)
(0, 6)
(1, 7)
(2, 8)
(3, 9)
(4, 10)
(2, 11)
(3, 12)

(最後の行には 2 ～ 3 の項目があり、0 ～ 1 および 4 に空のスペース/ギャップがあるのに対し、ys を使用したソリューションにはサイズ 1 のギャップしかないため、これは最適ではありません)

また、あなたの例とは一致しませんが (ゼロベースのインデックスでは 0、2、4 になります)、次の例は、ギャップ サイズが最小化されているため、これまでに定義したアルゴリズムを満たします。(1 と 3 にギャップがあるあなたのものではなく、インデックス 0 と 2 に 1 サイズのギャップ)0, 2, 4が実際に よりも優れている場合は、その理由を1, 3, 4正確に決定し、それをアルゴリズム定義に追加する必要があります。

Console.WriteLine(string.Join("\r\n", SplitItems(Enumerable.Range(1, 3), 5)));
// prints
(1, 1)
(3, 2)
(4, 3)

実際、これは一種の制限付きパーティションの問題です。d時間ごとにアイテムを分割する場合、可能な限り最小の部分を超えないhパーティションを検索する必要があります。たとえば、2 つの項目を 5 時間で分割する場合: 最適な解は 1+1+1です。これは、部分が 3 つ以下であるためです。これが最善の方法です。解が一つではない例として、5時間で3項目が1+1になっていますが、 、 、など、並べ方はさまざまです。h-dh-dmax(parts)max(parts) == 10,2,41,3,40,2,3

于 2013-11-14T14:43:28.607 に答える