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.

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

}

CodePudding user response：

I think this is close:

List<Box> boxes = new List<Box>
{
    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 pq = new PriorityQueue<Box, float>();

var floor = float.MinValue;
foreach (var box in boxes)
{
    pq.Enqueue(box, box.amount < 5f ? floor : box.amount);
    floor *= 0.9f;
}

while (boxes.Sum(b => b.amount) < 52f)
{
    var box = pq.Dequeue();
    box.amount  = 1.0f;
    pq.Enqueue(box, box.amount < 5f ? floor : box.amount);
    floor *= 0.9f;
    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, 5, 6, 5, 5
5, 5, 5, 5, 6, 5, 5, 6, 5, 5

CodePudding user response：

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

CodePudding user response：

Seems you need priority queue. I can see that dotnet contains implementation in System.Collections.

So put pairs index/value into a queue, provide comparer to make min-queue (perhaps default one).

At every step extract pair with the lowest value, increment corresponding array entry (by index) and put pair back to the queue.

I am not fluent in C# generics, so cannot give good example