1

我有可变数量的项目，我想在可变的时间范围内传播。我遇到的问题是如何分配剩余部分，以使“悬垂”之间的空间尽可能相等。例如，如果我有 13 个项目 (X) 分布在 5 个小时内，我想最终得到

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 件物品，我想以 Xs 结束 2 件物品和 Ys 1 件物品和 Zs

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

      y         y

           z

项目数和小时数是可变的。

好的，我想我目前走在正确的轨道上。我现在正试图将垃圾箱分成两半，并将剩余的一个放在中心垃圾箱中。这会递归地重复，直到余数为 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的 s 这样的虚拟值）在某些情况下它不会选择最佳间距，但我认为它总是很接近（即间隙不超过必要的 1） ，并始终返回正确数量的项目。

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），但以下示例满足您迄今为止定义的算法，因为它最小化了间隙大小。（索引 0 和 2 处的 1 大小间隙，而不是您的，在 1 和 3 处有间隙）如果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，您希望找到一个h-d不超过h-d部分的分区，max(parts)它可以是最小的。例如，在 5 个小时中划分 2 项：最优解是 1+1+1，因为它不超过 3 个部分，并且max(parts) == 1，这是你能做的最好的。以没有单一解的例子为例，5 小时中的 3 项有 1+1，但有不同的排列方式，包括0,2,4、1,3,4和0,2,3。

于 2013-11-14T14:43:28.607 回答