What is the optimal way to generate a set of integers, each as close as possible to Y, whose sum is X?

156 views Asked by At

X can be a positive decimal or integer and Y is a positive integer. X >= 2 * Y. What is the optimal way (in terms of code performance) to accomplish this?

Context

I am creating a damage over time (DoT) batching algorithm for a game. X is the total duration of the DoT effect and Y is the desired duration (size) of each batch.

If you simply take X / Y you usually end up with a remainder, which introduces significant rounding error. So I want to find a set of numbers that adds up to the X, but wherein each number is as close as possible to Y.

Current Solution

totalDuration is X and batchTarget is Y. BatchDurations is a List of integers containing the batches (the output of the function).

public void CalcBatchRate(float ticksPerUpdate, int batchTarget)
{
    float totalDuration = Effect.Duration * ticksPerUpdate;
    float batches = totalDuration / batchTarget;
    float batchesRemainder = batches % 1;
    float batchSize = batchTarget;

    if (batchesRemainder != 0)
    {
        batches -= batchesRemainder;
        batchSize = totalDuration / batches;

        // Check if adding another batch improves batch size:
        while (Math.Abs(batchSize - batchTarget) > Math.Abs((totalDuration / (batches + 1)) - batchTarget))
        {
            batches++;
            batchSize = totalDuration / batches;
        }

        // Correct for decimals:
        float batchSizeRemainder = batchSize % 1;
        if (batchSizeRemainder != 0)
        {
            // Based on the size of the remainder, determine how many batches to round up/down:
            int roundDown = (int)Math.Round(batches * Math.Abs(1 - batchSizeRemainder), 0);
            int roundUp = (int)(batches - roundDown);

            for (int i = roundDown; i > 0; i--)
            {
                BatchDurations.Add((int)(batchSize - batchSizeRemainder));
            }

            for (int i = roundUp; i > 0; i--)
            {
                BatchDurations.Add((int)(batchSize + (1 - batchSizeRemainder)));
            }
        }
        else
        {
            for (int i = (int)batches; i > 0; i--)
            {
                BatchDurations.Add((int)batchSize);
            }
        }
    }
    else
    {
        for (int i = (int)batches; i > 0; i--)
        {
            BatchDurations.Add((int)batchSize);
        }
    }
}
1

There are 1 answers

1
n. m. could be an AI On

Not sure what exactly you are trying to calculate, but here's some Python code.

def subdivide(totalDuration, batchTarget):

  print (f'Aiming to have total duration of {totalDuration} with batches of size {batchTarget}')

  nBatches = totalDuration // batchTarget
  totalError = totalDuration % batchTarget

  if totalError > batchTarget - totalError:
      nBatches = nBatches + 1
      totalError = totalError - batchTarget

  error = totalError // nBatches
  extraNum = totalError % nBatches
  regularNum = nBatches - extraNum
  regularSize = batchTarget + error
  extraSize = regularSize + 1

  checkTotalDuration = regularNum * regularSize + extraNum * extraSize

  print (f'{regularNum} batches of size {regularSize} and {extraNum} batches of size {extraSize}')
  print (f'have total duration of {checkTotalDuration}')