Проблема равномерного и упорядоченного распределения

У меня есть заданное количество коробок в определенном порядке и количество весов в определенном порядке. Гири могут иметь разный вес (т.е. один может весить 1 кг, другой 2 кг и т.д.). Я хочу положить гири в коробки таким образом, чтобы они были как можно более равномерно распределены по весу. Я должен взять гири в том порядке, в котором они даны, и я должен заполнить ящики в том порядке, в котором они даны. То есть, если я положу гирю в коробку n+1, я не смогу положить гирю в коробку n, а я не смогу положить в коробку гирю m+1, пока я сначала не положу в коробку гирю m.

Мне нужно найти алгоритм, решающий эту задачу для любого количества ящиков и любого набора весов.

Несколько тестов на C# с помощью xUnit (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]);
    }

Любая помощь приветствуется!


algorithm distribution
person Joel Abrahamsson    schedule 17.08.2009    source источник

Ответы (2)


arrow_upward
3
arrow_downward

См. решение ниже.

Ваше здоровье,

Марас

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];
            }
        }
    }
}
person Marek Musielak    schedule 17.08.2009
comment
Я был готов поспорить с вами, но ваше решение хорошее, если вы используете предположение о том, что ОП означает равномерное распределение. Хорошая работа! - person San Jacinto; 17.08.2009
comment
На самом деле, если подумать, [2, 17, 1, 1] на самом деле было бы лучше в этом случае, поскольку то, что я на самом деле пытаюсь сделать, это удовлетворить дизайнера. Есть ли шанс изменить свое решение? ;-) - person Joel Abrahamsson; 18.08.2009
comment
Привет, Джоэл. Какое решение лучше в этом случае: 4 коробки, весит [18, 1, 18, 6, 6]? решение1: [18, 19, 6, 6] решение2: [18, 1, 18, 12] и почему? - person Marek Musielak; 18.08.2009
comment
Я бы сказал [18, 19, 6, 6], так как максимальное отклонение от среднего (12,25) в этом случае ниже. - person Joel Abrahamsson; 19.08.2009

arrow_upward
2
arrow_downward

Вторая попытка: я думаю, что алгоритм A* (произносится как «звезда») будет работать здесь хорошо, даже если он будет потреблять много памяти. вы гарантированно получите оптимальный ответ, если таковой существует.

Каждый «узел», который вы ищете, представляет собой возможную комбинацию весов в ящиках. Первым узлом должен быть любой вес, который вы выберете наугад и положите в коробку. Я бы порекомендовал выбирать новые веса случайным образом.

К сожалению, A* настолько сложен, что у меня нет времени объяснять его здесь. Это достаточно легко понять, прочитав самостоятельно, но сопоставить это с этой проблемой, как я описал выше, будет сложнее. Пожалуйста, отправьте вопросы по этому поводу, если вы выберете этот маршрут.

person San Jacinto    schedule 17.08.2009