Как решить этот рюкзак с динамическим программированием?

Вопрос:

Для N объектов и 1~n объем i-го объекта равен ti и ti <= M; Между тем, есть много ящиков, а объем каждого окна – M Теперь мы должны поместить все эти объекты в коробки с порядком 1 ~ N, каково минимальное количество ящиков?

Например, существует 5 объектов, и их объем {7,2,5,3,9} с порядком 1 ~ 5. Объем каждого ящика равен 10. Таким образом, оптимальное решение – 3 ящика, и они {7},{2,5,3},{9} соответственно.

Мое решение: жадный алгоритм. Предположим, что оптимальное решение i-го объекта заполнено x-полями, а оставшееся пространство – y, то для объекта я + 1, если его объем больше y, его нужно поместить в другой новый ящик. В противном случае одним из вариантов является то, что он помещается в текущее поле, а решение (x, yv); другой вариант заключается в том, что он помещается в другой новый ящик, а решение (x + 1, Mv).

Вопрос: Как его решить с помощью динамического программирования?

Лучший ответ:

Я не понимаю, почему вы хотите решить это с помощью DP, так как у вас есть совершенно хорошее жадное решение, но вот идея на основе DP:

Пусть F(k) – ответ для первых k объектов – минимальное количество ящиков, в которые мы можем поместить их. Давайте рассмотрим, сколько объектов мы помещаем в последнем поле:

F(k) = min{F(l) + 1|l < k, t_(l+1) + t_(l+2) + .. + t_(k) <= M}
F(0) = 0

Сложность – O(N*N) если мы вычисляем суммы t_i на лету” для каждого k

Оцените статью
TechArks.Ru
Добавить комментарий