Распределение загрузки на грузовики

28. Распределить грузы по грузовикам с минимальной недогруженностью

Условие задачи:
Необходимо реализовать метод calcTrucks(), который принимает:

массив весов грузов weights;
количество грузовиков trucksCount;
максимальную грузоподъёмность одного грузовика truckMaxCapacity.

Каждый груз можно загрузить не более одного раза. Если груз невозможно или невыгодно разместить, его можно пропустить.

Нужно распределить грузы так, чтобы суммарный вес размещённых грузов был максимальным, а значит, суммарная недогруженность всех грузовиков — минимальной.

Метод должен вернуть:

trucksCount * truckMaxCapacity - суммарный вес размещённых грузов

Код:

private int calcTrucks(
        int[] weights,
        int trucksCount,
        int truckMaxCapacity
) {
    // TODO
}

Пример 1:

weights = [10, 100, 20, 30, 40, 10]
trucksCount = 4
truckMaxCapacity = 100

Общая вместимость: 400
Вес размещённых грузов: 210

Результат: 190

Пример 2:

weights = [10, 100, 20, 30, 40]
trucksCount = 4
truckMaxCapacity = 100

Общая вместимость: 400
Вес размещённых грузов: 200

Результат: 200

Спойлеры к решению

Подсказки

💡 Минимизировать свободное место — то же самое, что максимизировать суммарный вес загруженных грузов.
💡 Жадный алгоритм вроде Best Fit Decreasing может дать хороший результат, но не гарантирует минимум недогруженности.
💡 Для точного решения можно использовать перебор с возвратом (backtracking).
💡 Сортировка грузов по убыванию позволяет раньше рассматривать тяжёлые грузы.
💡 Грузовики с одинаковым остатком вместимости эквивалентны — повторно рассматривать такие состояния не нужно.

Решение

private static int calcTrucks(
        int[] weights,
        int trucksCount,
        int truckMaxCapacity
) {
    int[] sorted = Arrays.copyOf(weights, weights.length);
    Arrays.sort(sorted);

    for (int left = 0, right = sorted.length - 1;
         left < right;
         left++, right--) {

        int temp = sorted[left];
        sorted[left] = sorted[right];
        sorted[right] = temp;
    }

    int[] remaining = new int[trucksCount];
    Arrays.fill(remaining, truckMaxCapacity);

    int maxLoaded = findMaxLoaded(sorted, 0, remaining);

    return trucksCount * truckMaxCapacity - maxLoaded;
}

private static int findMaxLoaded(
        int[] weights,
        int index,
        int[] remaining
) {
    if (index == weights.length) {
        return 0;
    }

    int weight = weights[index];

    // Вариант: не загружать текущий груз
    int best = findMaxLoaded(weights, index + 1, remaining);

    Set<Integer> usedRemaining = new HashSet<>();

    for (int i = 0; i < remaining.length; i++) {
        if (remaining[i] < weight) {
            continue;
        }

        // Грузовики с одинаковым свободным местом
        // приводят к одинаковым состояниям.
        if (!usedRemaining.add(remaining[i])) {
            continue;
        }

        remaining[i] -= weight;

        best = Math.max(
                best,
                weight + findMaxLoaded(
                        weights,
                        index + 1,
                        remaining
                )
        );

        remaining[i] += weight;
    }

    return best;
}

Ключевое наблюдение:

недогруженность =
общая вместимость - загруженный вес

Общая вместимость постоянна:

trucksCount * truckMaxCapacity

поэтому достаточно найти максимально возможный вес грузов, которые можно разместить.

Для каждого груза рассматриваются варианты:

1. пропустить груз;
2. положить в первый подходящий грузовик;
3. положить во второй подходящий грузовик;
...

После рекурсивного вызова состояние грузовика восстанавливается:

remaining[i] -= weight;

// рекурсивный поиск

remaining[i] += weight;

Это классический backtracking.

Проверка:

if (!usedRemaining.add(remaining[i])) {
    continue;
}

отсекает симметричные варианты. Например, если три пустых грузовика имеют по 100 свободного места, нет смысла пробовать один и тот же груз отдельно в каждом из них — состояния будут эквивалентны.

Для первого примера все грузы можно разместить:

100
40 + 30 + 20 + 10
10
пустой грузовик

Общий загруженный вес:

поэтому:

400 - 210 = 190

Для второго примера суммарный вес грузов равен 200, и все они также помещаются:

400 - 200 = 200

Задача в общем случае относится к NP-трудным задачам упаковки. Поэтому точный алгоритм имеет экспоненциальную сложность в худшем случае. Если количество грузов очень велико и допустимо приближённое решение, можно использовать эвристику Best Fit Decreasing, но она не гарантирует минимальную недогруженность.