如何在整数列表中分配一个值，优先将整数填充到软上限

Question

我正在尝试解决填充列表中的每个项目直到每个项目都达到上限的概念。一旦每个项目都达到 ceiling/limit 任何剩余的多余值就会从列表的第一项开始再次分配。当前细分后的示例。

我相信我对问题的第一个组成部分有一个解决方案，分配值 - 但是我不确定处理多余值的解决方案。

详细示例：

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.

在下面的table中，init是每个盒子中存储的预先存在的值。接下来的列显示了值 25、33 和最后 40 在方框中的分布。在 40 中，您可以更清楚地看到填充最空框的优先级如何优先于最终填充所有其他框。

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

我现在的逻辑是这样的：


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

我认为这很接近：

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

这给了我：

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

这似乎是二元的；您必须分配的金额将完全填满方框（with/out 溢出），或者不会。如果会，则从它们全部开始并分配溢出的部分，否则，分配到一个上限

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

如果您想要一种优先考虑最空框的逻辑，使用 MinBy（.net6 或 MoreLinq）会变得更简单

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

在旧的 .net 中是 boxes.First(b => b.Amount == boxes.Min(b2 => b2.Amount) ).Amount++;

对此进行优化和调整的空间很大，但值得付出多少努力取决于它的热点程度

如何在整数列表中分配一个值，优先将整数填充到软上限

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

c#

math