An even and sorted distribution problem

Question

I have a given number of boxes in a specific order and a number of weights in a specific order. The weights may have different weights (ie one may weigh 1kg, another 2kg etc). I want to put the weights in the boxes in a way so that they are as evenly distributed as possible weight wise. I must take the weights in the order that they are given and I must fill the boxes in the order that they are given. That is if I put a weight in box n+1 I cannot put a weight in box n, and I cannot put weight m+1 in a box until I've first put weight m in a box.

I need to find an algorithm that solves this problem for any number of boxes and any set of weights.

A few tests in C# with xUnit (Distribute is the method that should solve the problem):

    [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]);
    }

Any help is greatly appreciated!

Answer 1

Second try: i think the A* (pronounced "a star") algorithm would work well here, even if it would consume a lot of memory. you are guranteed to get an optimal answer, if one exists.

Each "node" you are searching is a possible combination of weights in boxes. The first node should be any weight you pick at random, put into a box. I would recommend picking new weights randomly as well.

Unforetunately, A* is complex enough that I don't have time to explain it here. It is easy enough to understand by reading on your own, but mapping it to this problem as I described above will be more difficult. Please post back questions on that if you choose this route.

Answer 2

Hi Joel,

See the solution below.

Cheers,

Maras

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];
            }
        }
    }
}