Упаковка предметов с двух концов ряда в несколько грузовиков

В ряду есть предметы, которые нужно поместить в несколько грузовиков. Вес предметов и количество грузовых автомобилей и их общая вместимость приведены. Предметы можно перемещать в грузовики только с двух концов ряда. Как мы можем определить максимальное количество предметов, которые можно поместить в грузовики?
(Максимум 10000 предметов и 100 грузовиков.)

Пример:
Предметы: (20, 70, 10, 30, 80, 60, 50, 30)
Количество грузовых автомобилей: 3
Вместимость грузовых автомобилей: 100

Здесь мы можем разместить до 7 предметов, например, так:

item    to truck  remaining
 20     1         (70, 10, 30, 80, 60, 50, 30)
 30     2         (70, 10, 30, 80, 60, 50)
 70     2         (10, 30, 80, 60, 50)
 50     1         (10, 30, 80, 60)
 10     3         (30, 80, 60)
 30     1         (80, 60)
 60     3         (80)

Моя идея состояла бы в том, чтобы попытаться заполнить все грузовики как можно больше, но проблемы с упаковкой для меня новы, и я очень мало знаю о них.

Источник

1 ответ

Проблема действительно может быть решена с помощью динамического программирования; Однако это может быть трудно без предыдущего опыта с подходом. Отношение рекуррентности и пространство состояний можно определить следующим образом.

Позволять n обозначить количество предметов и i_1,...,i_n их размеры; позволять m обозначим количество грузовиков и пусть c_1,...,c_m обозначить их возможности. Пространство состояний может быть реализовано как m+2таблица, где вход в позицию (k_1,k_2,l_1,...,l_m) определяется как максимально возможное количество предметов, выбранных из дополнения предметов {k_1,...,k_2} (который тогда является оставшейся очередью предметов), где грузовик k имеет оставшийся груз точно l_k или отрицательной бесконечности такого решения не существует. После инициализации состояний, соответствующих базовым случаям, пространство состояний может быть оценено итеративно с использованием рекуррентного отношения

(k_1,k_2,l_1,...,l_m) = max
                        {
                            (k_1+1,k_2,l_1,...,l_m),
                            (k_1,k_2+1,l_1,...,l_m),

                            (k_1+1,k_2,l_1-i_k_1,...,l_m) + 1, m cases in total
                            ...,
                            (k_1+1,k_2,l_1,...,l_m-i_k_1) + 1,

                            (k_1,k_2-1,l_1-i_k_2,...,l_m) + 1, m cases in total
                            ...,
                            (k_1,k_2-1,l_1,...,l_m-i_k_2) + 1,
                        }

где первые два случая соответствуют отбрасыванию левого конца и правого конца очереди, следующий m случаи соответствуют упаковке товара в левом конце очереди к каждому из m грузовики и последнее m случаи соответствуют упаковке товара в правом конце очереди к каждому из m грузовые автомобили.

После оценки пространства состояний необходимо изучить все конечные состояния; это те, в которых каждый предмет либо упакован, либо выброшен. Эти государства те, для которых k_1 = k_2-1 держит, то есть очередь будет пустой. Реализация будет принимать максимальное значение из них; если результат отрицательный бесконечность, никакого допустимого решения не существует.

Источник
Другие вопросы по тегам