4

我有特定顺序的给定数量的盒子和特定顺序的重量。重量可能有不同的重量（即一个可能重 1 公斤，另一个可能重 2 公斤等）。我想以某种方式将重量放在盒子中，以便它们在重量方面尽可能均匀分布。我必须按照给出的顺序取重量，我必须按照给出的顺序填满箱子。也就是说，如果我在盒子 n+1 中放了一个重量，我就不能在 n 盒子里放一个重量，而且在我首先将重量 m 放入一个盒子之前，我不能将重量 m+1 放入一个盒子中。

我需要找到一种算法来解决任意数量的盒子和任意一组权重的这个问题。

使用 xUnit 在 C# 中进行一些测试（分发是应该解决问题的方法）：

    [Fact]
    public void ReturnsCorrectNumberOfBoxes()
    {
        int[] populatedColumns = Distribute(new int[0], 4);

        Assert.Equal<int>(4, populatedColumns.Length);
    }

    [Fact]
    public void Test1()
    {
        int[] weights = new int[] { 1, 1, 1, 1 };

        int[] boxes = Distribute(weights, 4);

        Assert.Equal<int>(weights[0], boxes[0]);
        Assert.Equal<int>(weights[1], boxes[1]);
        Assert.Equal<int>(weights[2], boxes[2]);
        Assert.Equal<int>(weights[3], boxes[3]);
    }

    [Fact]
    public void Test2()
    {
        int[] weights = new int[] { 1, 1, 17, 1, 1 };

        int[] boxes = Distribute(weights, 4);

        Assert.Equal<int>(2, boxes[0]);
        Assert.Equal<int>(17, boxes[1]);
        Assert.Equal<int>(1, boxes[2]);
        Assert.Equal<int>(1, boxes[3]);
    }

    [Fact]
    public void Test3()
    {
        int[] weights = new int[] { 5, 4, 6, 1, 5 };

        int[] boxes = Distribute(weights, 4);

        Assert.Equal<int>(5, boxes[0]);
        Assert.Equal<int>(4, boxes[1]);
        Assert.Equal<int>(6, boxes[2]);
        Assert.Equal<int>(6, boxes[3]);
    }

任何帮助是极大的赞赏！

4

2 回答 2

3

请参阅下面的解决方案。

干杯，

马拉斯

public static int[] Distribute(int[] weights, int boxesNo)
{
    if (weights.Length == 0)
    {
        return new int[boxesNo];
    }

    double average = weights.Average();

    int[] distribution = new int[weights.Length];

    for (int i = 0; i < distribution.Length; i++)
    {
        distribution[i] = 0;
    }

    double avDeviation = double.MaxValue;

    List<int> bestResult = new List<int>(boxesNo);


    while (true)
    {
        List<int> result = new List<int>(boxesNo);

        for (int i = 0; i < boxesNo; i++)
        {
            result.Add(0);
        }

        for (int i = 0; i < weights.Length; i++)
        {
            result[distribution[i]] += weights[i];
        }
        double tmpAvDeviation = 0;

        for (int i = 0; i < boxesNo; i++)
        {
            tmpAvDeviation += Math.Pow(Math.Abs(average - result[i]), 2);
        }
        if (tmpAvDeviation < avDeviation)
        {
            bestResult = result;
            avDeviation = tmpAvDeviation;
        }

        if (distribution[weights.Length - 1] < boxesNo - 1)
        {
            distribution[weights.Length - 1]++;
        }
        else
        {
            int index = weights.Length - 1;
            while (distribution[index] == boxesNo - 1)
            {
                index--;
                if (index == -1)
                {
                    return bestResult.ToArray();
                }
            }
            distribution[index]++;
            for (int i = index; i < weights.Length; i++)
            {
                distribution[i] = distribution[index];
            }
        }
    }
}
于 2009-08-17T16:14:41.507 回答
2

第二次尝试：我认为 A*（发音为“a star”）算法在这里可以很好地工作，即使它会消耗大量内存。如果存在最佳答案，您一定会得到最佳答案。

您正在搜索的每个“节点”都是框内权重的可能组合。第一个节点应该是您随机选择的任何重量，放入一个盒子中。我也建议随机选择新的权重。

不幸的是，A* 太复杂了，我没有时间在这里解释它。通过自己阅读很容易理解，但是如上所述将其映射到这个问题会更加困难。如果您选择这条路线，请回复有关该问题的问题。

于 2009-08-17T15:19:36.130 回答