Блог

Я пытаюсь решить следующую проблему (аналогичную названию): Разделите массив на минимальное количество поддиапазонов таким образом, чтобы каждый поддиапазон имел сумму в диапазоне [w, W], обратите внимание, что вы не можете изменить порядок массива. Я думаю, что мне нужно было бы использовать DP с 2D пространством состояний, но я, кажется, не совсем понимаю это.

Любая помощь в этом будет признательна!

Для DP достаточно массива 1d. Назовите его arr, и пусть arr[i] представляет решение той же проблемы, ограниченное первыми i элементами.

Инициализируйте arr[i] = бесконечность для i s.t. сумма элементов до amp; включая i равна lt; w, и 1, если сумма gt;= w и lt; w, и 1, если сумма gt;

Решите для каждого неизвестного значения i в порядке возрастания, рассмотрев все допустимые подмассивы, заканчивающиеся на i, взяв минимальное значение для всех из них, хранящихся в arr, за последний elt до начала допустимого подмассива и увеличив его на 1.

Например, w=3, W=5, вход = 2,2,3,4,2,1,1,5

 initialize: arr = [inf, 1, ...] input[2]: arr = [inf, 1, 2, ...] input[3]: arr = [inf, 1, 2, 3, ...] input[4]: arr = [inf, 1, 2, 3, inf, ...] input[5]: arr = [inf, 1, 2, 3, inf, 4, ...] input[6]: arr = [inf, 1, 2, 3, inf, 4, 4, ...] input[7]: arr = [inf, 1, 2, 3, inf, 4, 4, 5]  

Решение: [2,2], [3], [4], [2,1,1], [5]