Изменение рюкзака (или раздела) алгоритма

Question

вопрос У меня проблема заключается в следующем:

Учитывая очередь из N элементов, каждый из которых имеет вес, и очередь контейнеров K. И нам нужно разбить предметы на контейнеры в том порядке, в котором они были. Например, самый первый элемент может перейти только к первому контейнеру, второй - к первому или второму, но не к третьему (в противном случае второй контейнер не будет иметь никаких элементов).

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

Я полагаю, что это какая-то вариация проблемы с 3-разделами или рюкзаками. Я уже реализовал одно возможное решение для распространения с помощью динамического программирования и попытался получить счет из используемой в нем таблицы. Но это было недостаточно эффективно (слишком дорогое количество памяти), и алгоритм получения количества контейнеров был неправильным.

Может кто-нибудь объяснить, пожалуйста, какой алгоритм является решением этой проблемы?

Answer 1

Таким образом, проблема ОП в общем случае может быть решена с помощью алгоритма DP, приведенного в this question. Я повторю суть его здесь для полноты картины:

Предположит г [я] [J] является решением проблемы, когда мы имеем деталь s [1], .., s [я] и j контейнеры. Тогда:

1. д [0] [J] = 0 для каждого J
2. D [I] [1] = Сумма (с [1], ..., s [I ]) для каждый я
3. d [I] [J] = мин (макс (д [его] [J-1], Сумма (с [его + 1], ..., s [i]) по всем 1 < = t < = i)

Однако наивная реализация требует пространства O (NK), что слишком много. К счастью, посмотрите (3): d[_][j] значение зависит только от d[_][j-1]. Это означает, что как только мы закончим вычислять все d[_][j], мы можем использовать пространство, которое мы использовали для хранения d[_][j-1], вместо этого сохраним значения d[_][j+1], которые мы собираемся вычислить.

Поскольку значения d[0][j] равны нулю, нам также не нужно их хранить. Следовательно, единственными массивами, которые нам нужно сохранить, являются O (N) -размер d[i][1], массив с O (N), который содержит результат от j-1-й итерации, а массив с O (N), который содержит результаты из j-й итерации, которую мы сейчас вычислим. Итого: O (N).

Редактировать: Итак, в первый раз, я фактически не ответил на вопрос о том, как подсчитать количество контейнеров при максимальном весе. Предположим, что w[i][j] содержит максимальный вес проблемы i,j, а c[i][j] - количество контейнеров, которые соответствуют этому максимальному весу.Тогда:

1. c[0][j] = j и w[0][j] = 0 для каждого j
2. c[i][1] = 1 и w[i][1] = Sum(s[1], .., s[i]) для каждого i
3. Пусть u быть равен t выбранного в п (3) выше.
   • Если d[i-u][j-1] > Sum(s[i-u+1], .., s[i]):
     • затем c[i][j] = c[i-u][j-1] и w[i][j] = w[i-u][j-1]
     • потому что j го контейнера с весом Sum(s[i-u+1], .., s[i] легче, чем тяжелый контейнер из контейнеров 1, .., j-1, который имеет вес d[i-u][j-1].
   • Если d[i-u][j-1] < Sum(s[i-u+1], .., s[i]):
     • затем c[i][j] = 1 и w[i][j] = Sum(s[i-u+1], .., s[i])
     • потому j го контейнера с элементами s[i-u+1], .., s[i] является новый тяжелый контейнер.
   • Если Если d[i-u][j-1] == Sum(s[i-u+1], .., s[i]):
     • затем c[i][j] = c[i-u][j-1]+1 и w[i][j] = d[i-u][j-1]
     • потому что j-й контейнер является такой же вес, как и предыдущий тяжелый контейнер.

Опять же, нам нужно только использовать постоянное число O(N) размера массивов, для O(N) времени в целом.