4

特定の順序で指定された数のボックスと特定の順序でいくつかのウェイトがあります。重りの重さは異なる場合があります（つまり、1つは1kg、もう1つは2kgなど）。ウェイトをできるだけ均等に分散するようにボックスに入れたいと思います。与えられた順序で重みを取り、与えられた順序でボックスに入力する必要があります。つまり、ボックスn + 1にウェイトを入れると、ボックスnにウェイトを入れることができず、最初にウェイトmをボックスに入れるまで、ウェイトm+1をボックスに入れることができません。

任意の数のボックスと任意の重みのセットに対してこの問題を解決するアルゴリズムを見つける必要があります。

xUnitを使用したC＃でのいくつかのテスト（Distributeは問題を解決する方法です）：

    [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

2 回目の試行: A* (「スター」と発音) アルゴリズムは、大量のメモリを消費する場合でも、ここではうまく機能すると思います。最適な答えが存在する場合は、それが得られることが保証されています。

検索している各「ノード」は、ボックス内の重みの可能な組み合わせです。最初のノードは、ランダムに選択してボックスに入れる任意の重みにする必要があります。新しい重みもランダムに選ぶことをお勧めします。

残念ながら、A* は非常に複雑なので、ここで説明する時間はありません。自分で読んで理解するのは簡単ですが、上で説明したようにこの問題にマッピングするのはより困難です。このルートを選択した場合は、質問を投稿してください。

于 2009-08-17T15:19:36.130 に答える