How do I distribute a value across a list of integers, with a priority to fill the integers to a soft-cap first

Question

I am trying to solve the concept of filling every item in a list until every item has reached a ceiling. Once every item has reached a ceiling/limit any remaining excess values is then distributed once more starting from the first item of the list. Examples after the current breakdown.

I believe I have a solution for the first component of the problem, distributing values - however I am unsure of the solution to dealing with excess values.

A detailed example:

I have a list of boxes (10 boxes) and a value of 33 products, I want to distribute the products one at a time across these boxes until a limit ceiling for each box is set (5 products). Every box must be filled to 5 before I pick my first box again and start one at a time to add the remaining excess.

In the table below, init is the pre-existing values stored in each box. The next columns show distribution across the boxes for values of 25,33, and finally 40. In 40 you can see more clearly how priority of filling in the emptiest boxes preceeds eventually filling every other box in.

init	25	33	40
2	4	5	6
1	3	5	6
2	4	5	5
0	2	4	5
-1	1	3	5
2	4	5	5
3	5	5	5
0	2	4	5
2	4	5	5
1	3	4	5

My current logic is this:

class Box
{
    public float amount;
}

public static void Init()
{
    // Create a list of boxes.

    List<Box> boxes = new List<Box>
    {
        // Add boxes to the list.
        new Box() { amount = 2 },
        new Box() { amount = 1 },
        new Box() { amount = 2 },
        new Box() { amount = 0 },
        new Box() { amount = -1 },
        new Box() { amount = 2 },
        new Box() { amount = 3 },
        new Box() { amount = 0 },
        new Box() { amount = 2 },
        new Box() { amount = 1 }
    };

    Distribute(boxes, 25, 2);

}

static void Distribute(List<Box> boxes, float totalValue, float maxDistribution)
{
    float ceiling = 5; //The "soft limit" for each box.

    List<Box> currentBoxes = boxes;
    List<Box> criticalBoxes = new List<Box>();

    int distribution = (int)(totalValue / maxDistribution); //amount of times needed for even distribution.
    int currentBoxIndex = 0;

    for (int i = 0; i < distribution; i++)
    {

        //If we have room, add distribution, else move to a "at capacity list"
        if (currentBoxes[currentBoxIndex].amount + maxDistribution < ceiling)
        {
            currentBoxes[currentBoxIndex].amount += maxDistribution; //Distribute the maximum allowed per loop
        } else
        {
            criticalBoxes.Add(currentBoxes[currentBoxIndex]);
            currentBoxes.RemoveAt(currentBoxIndex);
        }

        //Status of loop.
        if(currentBoxIndex == currentBoxes.Count)
        {
            currentBoxIndex = 0;
        } else
        {
            currentBoxIndex++;
        }
    }

}

Answer 1

I think this is close:

List<Box> boxes = new List<Box>
{
    // Add boxes to the list.
    new Box() { amount = 2 },
    new Box() { amount = 1 },
    new Box() { amount = 2 },
    new Box() { amount = 0 },
    new Box() { amount = -1 },
    new Box() { amount = 2 },
    new Box() { amount = 3 },
    new Box() { amount = 0 },
    new Box() { amount = 2 },
    new Box() { amount = 1 }
};

Console.WriteLine(String.Join(", ", boxes.Select(b => b.amount)));

var sorted = boxes.OrderBy(b => b.amount < 5f ? int.MinValue : b.amount).ToList();

while (boxes.Sum(b => b.amount) < 52f)
{
    var box = sorted.First();
    sorted.RemoveAt(0);
    box.amount += 1.0f;
    sorted = sorted.Append(box).OrderBy(b => b.amount < 5f ? int.MinValue : b.amount).ToList();
    Console.WriteLine(String.Join(", ", boxes.Select(b => b.amount)));
}

That gives me:

2, 1, 2, 0, -1, 2, 3, 0, 2, 1
3, 1, 2, 0, -1, 2, 3, 0, 2, 1
3, 2, 2, 0, -1, 2, 3, 0, 2, 1
3, 2, 3, 0, -1, 2, 3, 0, 2, 1
3, 2, 3, 1, -1, 2, 3, 0, 2, 1
3, 2, 3, 1, 0, 2, 3, 0, 2, 1
3, 2, 3, 1, 0, 3, 3, 0, 2, 1
3, 2, 3, 1, 0, 3, 4, 0, 2, 1
3, 2, 3, 1, 0, 3, 4, 1, 2, 1
3, 2, 3, 1, 0, 3, 4, 1, 3, 1
3, 2, 3, 1, 0, 3, 4, 1, 3, 2
4, 2, 3, 1, 0, 3, 4, 1, 3, 2
4, 3, 3, 1, 0, 3, 4, 1, 3, 2
4, 3, 4, 1, 0, 3, 4, 1, 3, 2
4, 3, 4, 2, 0, 3, 4, 1, 3, 2
4, 3, 4, 2, 1, 3, 4, 1, 3, 2
4, 3, 4, 2, 1, 4, 4, 1, 3, 2
4, 3, 4, 2, 1, 4, 5, 1, 3, 2
4, 3, 4, 2, 1, 4, 5, 2, 3, 2
4, 3, 4, 2, 1, 4, 5, 2, 4, 2
4, 3, 4, 2, 1, 4, 5, 2, 4, 3
5, 3, 4, 2, 1, 4, 5, 2, 4, 3
5, 4, 4, 2, 1, 4, 5, 2, 4, 3
5, 4, 5, 2, 1, 4, 5, 2, 4, 3
5, 4, 5, 3, 1, 4, 5, 2, 4, 3
5, 4, 5, 3, 2, 4, 5, 2, 4, 3
5, 4, 5, 3, 2, 5, 5, 2, 4, 3
5, 4, 5, 3, 2, 5, 5, 3, 4, 3
5, 4, 5, 3, 2, 5, 5, 3, 5, 3
5, 4, 5, 3, 2, 5, 5, 3, 5, 4
5, 5, 5, 3, 2, 5, 5, 3, 5, 4
5, 5, 5, 4, 2, 5, 5, 3, 5, 4
5, 5, 5, 4, 3, 5, 5, 3, 5, 4
5, 5, 5, 4, 3, 5, 5, 4, 5, 4
5, 5, 5, 4, 3, 5, 5, 4, 5, 5
5, 5, 5, 5, 3, 5, 5, 4, 5, 5
5, 5, 5, 5, 4, 5, 5, 4, 5, 5
5, 5, 5, 5, 4, 5, 5, 5, 5, 5
5, 5, 5, 5, 5, 5, 5, 5, 5, 5
5, 5, 5, 5, 5, 5, 6, 5, 5, 5
6, 5, 5, 5, 5, 5, 6, 5, 5, 5

Answer 2

It seems binary; either the amount you have to distribute will completely fill boxes (with/out overspill) or it won't. If it will, then start from them all full and distribute the overspill, otherwise, distribute to a cap

int distrib = 40;
int cap = 5;
int space = boxes.Sum(b => cap - b.Amount);
int overspill = distrib - space;

if(overspill >= 0){

  boxes.ForEach(b => b.Amount = cap + overspill / boxes.Count);
  distrib = overspill % boxes.Count;
  cap = int.MaxValue;
}


for(int x= 0; x < distrib;){
  var b = boxes[x%boxes.Count];
  if(b.Amount >= cap)
    continue;
  boxes[x%boxes.Count].Amount++;
  x++;
}

If instead you want a logic of prioritizing the emptiest boxes, it gets simpler with MinBy (.net6 or MoreLinq)

int distrib = 25;
while(distrib-- > 0)
  boxes.MinBy(b => b.Amount).Amount++;
  

In older .net that's boxes.First(b => b.Amount == boxes.Min(b2 => b2.Amount) ).Amount++;

There's plenty of scope for optimizing and tweaking this, but how much it's worth the effort depends on how much of a hot spot it is