Можно ли ограничить размер деталей в задаче линейного разбиения? - PullRequest
Новая
       38

Можно ли ограничить размер деталей в задаче линейного разбиения?

1 голос
/ 12 апреля 2020

У меня есть инженерная проблема, которая требует, чтобы я разбил набор положительных чисел на k частей, не меняя порядок чисел в наборе, чтобы суммы частей были как можно более равными. Я понял, что есть решения этой «проблемы линейного разбиения». На самом деле, я уже успешно попробовал решение для динамического программирования c, и оно работает.

Теперь вопрос: что, если существует ограничение максимального размера для деталей? («Ни одна деталь не может иметь более m элементов»). Может ли она быть добавлена, например, к решению DP, или можно использовать какую-то другую технику для решения этой проблемы.

Оцените все комментарии, ссылки и предложения.

Редактировать: я добавил грубый набросок исходного алгоритма ниже 

// Partition number array seq to k parts with max number of m items in each part
public void LinearPartition(double[] seq, int k, int m)
{
    double[,] table;
    int[,] solution;
    int n = seq.Length - 1;

    linearPartitionTable(seq, k, m, out table, out solution);

    k = k - 2;
    while (k >= 0)
    {
        Console.WriteLine(solution[n - 1, k] + 1);
        n = solution[n - 1, k];
        k--;
    }
}

private void linearPartitionTable(double[] seq, int k, int m, 
  out double[,] table, out int[,] solution)
{
    int n = seq.Length;

    table = new double[n, k];
    solution = new int[n - 1, k - 1];

    table[0, 0] = 0;
    for (int i = 1; i < n; i++)
        table[i, 0] = seq[i] + table[i - 1, 0];
    for (int j = 0; j < k; j++)
        table[0, j] = seq[0];

    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < k; j++)
        {
            double currentMin = double.MaxValue;
            int minX = 0;
            for (int x = 0; x < i; x++)
            {
                double cost = Math.Max(table[x, j - 1], table[i, 0] - table[x, 0]);
                if (cost < currentMin)
                {
                    currentMin = cost;
                    minX = x;
                }
            }
            table[i, j] = currentMin;
            solution[i - 1, j - 1] = minX;
        }
    }
}
...