Здравствуйте, Хабрахабр. В этом после я хочу рассказать о динамическом программировании на примере решения одной из задач. С этой задачей я недавно столкнулся на портале олимпиадных задач (ссылка указана в конце). Сразу перейду к делу.
Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.
Для построения модели трех кубиков он использовал 28 спичек.
Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?
Все числа в задаче не превышают 2·109.
Технические условия
Входные данные
Одно число N – количество кубиков.
Выходные данные
Одно число – количество спичек.
Я решил эту задачу используя динамическое программирование, но ее можно было решить и другими способа, и даже просто одной формулой — которую мы выведем в конце.
«Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.» — Класс задач которые решаются динамическим программированием.
И наша цель добиться решения, согласно описанию задач на динамическое программирование, в котором решение для текущих параметров строится на решении предыдущих.
Данную задачу я разбил на 3 этапа:
И так установим условия задачи:
Нам нужно узнать минимального количество спичек которое необходимо что бы построить линию из N квадратов со стороной в 1 спичку
Для хранения результата я буду использовать массив DP.
Теперь смотрим на рисунок и заполняем этот массив числами которые нужно прибавить к решению для i-1 случая:
И ответом для N будет сумма элементов массива DP от 0 до N, и сразу видим закономерность — для DP[1]:=4, DP[>1]:=3
и выводим формулу(N всегда > 1, т.е. натуральное):
Result(N):= SUM(DP1->DPN) = 4+(N-1)*3
Задача:
Нам нужно узнать минимального количество спичек которое необходимо для построения квадратов со стороной в 1 спичку. Строить можно в 2 измерениях.
В 2D у нас появляется новая проблема: к плоскости какого размера A х B нужно стремится что бы минимизировать количество спичек? И как многие догадались, это конечно же квадрат. Но не все так просто, там нужно упростить эту идею.
Если взглянуть на рисунок выше, то можно заметить что наиболее выгодным положением для нового квадрата будет то у которого больше соседей, и при оптимальном случае — это будет 2 соседа.
То есть оптимальным случаем будет строить так:
Мы можем легко сказать куда надо строить следующий кубик если будет это делать руками, но как об этом сказать компьютеру?
Если взять листочек и начать строить некую плоскость из квадратиком что бы минимизировать количество ребер, мы заметим как мы строим:
Первоначально это был квадратик 1х1 — 1 квадрат, дальше удлиняем на до 2х1 — 2 квадрата, дальше:
2х2 — 3 и потом 4 квадрата
3х2 — 5 и 6 квадратов
3х3 — 7,8,9 квадратов
Внимательно посмотрим и видим закономерность: мы имеем плоскость A x B чтобы минимизировать количество ребер, следующие для построения плоскости будут (A+1) x B и потом (A+1) x (B + 1), последняя является квадратом, так как мы начинаем строить из 1 х 1
Напишем таблицу для массива DP:
Анализируем таблицу:
для DP[1]=4
дальше когда мы добавляем новый ряд мы делаем новый квадрат используя 3 спички и до конца ряда достраиваем квадраты по 2 спички. Еще не чего не напоминает? Вспомним случай с 1D — первый квадрат 4 спички, остальные по 3, в данном случае это тот же дополнительный ряд, но с начальным квадратом в 3 спички и остальными в 2 спички.
Теперь алгоритм решения:
или так:
И формула:
Result(N):=4+3*(количество полных квадратов которые есть до числа N без 1 + дополнительные числа которые идут перед полными квадратами)+2*(все остальное)
NSQRT:= int(sqrt(N))-1
NADD:= NSQRT + 1(если N <= NSQRT*(NSQRT+1))
Result(N):=4+3*(NSQRT+NADD)+2*(N-NSQRT-NADD)
Вот добрались и до 3Д случая
В трехмерном случае, для минимализации количества спичек для построения, теперь уже, кубов нужно стремится к построению большого куба, но в промежуточных вариантах это будет:
A x B x C -> (A+1) x B x C -> (A+1) x (B+1) x C -> (A+1) x (B+1) x (C+1)
алгоритм решения будет таким же как и в 2D случае, но учитывая некоторые новые особенности:
1D(N):= 5+(N-1)*3
2D(N):= алгоритм приведенный выше в подразделе, но с корректировкой — 2D(1):= 8
3D(N):= алгоритм приведенный выше в 2D случае, но с учетом трехмерности — 3D(1):= 12, и при увеличение координат мы будем изменять результат так: Result:= Result + 2D(A*B*C/max(A,B,C)), т.е. нужно будет получать 2D от размера добавленной плоскости изменением параметром нашего нового параллелепипеда
И формула для 3D
Формула будет состоять из тех же частей что и формула для 2D, но также мы будет учитывать не только полные квадраты но и полные Кубы
Result(N):=12+8*(3*Nполные кубы+(0 или 1 или 2 в зависимости от N))+5*(2*Nполные квадраты+(0 или 1 в зависимости от N))+3*Nостальное
Но, к сожалению, эта формула не совсем правильна и требует большего умственного усилия для продумывания некоторых исключений и поправок.
В предыдущих разделах мы исследовали от чего зависит минимализация спичек для для куба/квадрата и опираясь на это мы можем сделать алгоритм любого измерения:
Нужно учитывать со скольких спичек состоит первоначальный N-мерный квадрат, и просчитать какое количество спичек нужно чтобы достраивать новые элементы
Алгоритм увлечения размерности объекта мы вывели — на каждой итерации увеличивать на 1 наименьшую размерность.
Также поняли что при изменении размера объекта к результату нужно прибавлять значение функции (N-1)-го измерения от размера добавленной плоскости
В при создании формулы нужно учитывать количество чисел в N степени, N-1, N-2 и т.д. + учитывать особенности
E-olimp — Интернет-портал организационно-методического обеспечения дистанционных олимпиад по программированию для одаренной молодежи учебных заведений Украины.
Задача на портале, которую можете попробовать сдать — нужна регистрация
Статья о динамическом программировании
Задача
Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.
Для построения модели трех кубиков он использовал 28 спичек.
Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?
Все числа в задаче не превышают 2·109.
Технические условия
Входные данные
Одно число N – количество кубиков.
Выходные данные
Одно число – количество спичек.
Я решил эту задачу используя динамическое программирование, но ее можно было решить и другими способа, и даже просто одной формулой — которую мы выведем в конце.
«Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.» — Класс задач которые решаются динамическим программированием.
И наша цель добиться решения, согласно описанию задач на динамическое программирование, в котором решение для текущих параметров строится на решении предыдущих.
Решение
Данную задачу я разбил на 3 этапа:
- Решить задачу для 1D случая и в нем буду использовать квадрат со стороной в 1 спичку, вывести формулу
- Решить задачу для 2D случая и в нем буду использовать квадрат со строной в 1 спичку, вывести формулу
- Найти закономерности в 1D и 2D случае и на их основе решить задачу для 3D случая, вывести формулу для 3D случая
- Мысли на счет n-мерного случая
1D
И так установим условия задачи:
Нам нужно узнать минимального количество спичек которое необходимо что бы построить линию из N квадратов со стороной в 1 спичку
Для хранения результата я буду использовать массив DP.
Теперь смотрим на рисунок и заполняем этот массив числами которые нужно прибавить к решению для i-1 случая:
| N: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| DP: | 0 | 4 | 3 | 3 | 3 | 3 | 3 | 3 |
И ответом для N будет сумма элементов массива DP от 0 до N, и сразу видим закономерность — для DP[1]:=4, DP[>1]:=3
и выводим формулу(N всегда > 1, т.е. натуральное):
Result(N):= SUM(DP1->DPN) = 4+(N-1)*3
2D
Задача:
Нам нужно узнать минимального количество спичек которое необходимо для построения квадратов со стороной в 1 спичку. Строить можно в 2 измерениях.
В 2D у нас появляется новая проблема: к плоскости какого размера A х B нужно стремится что бы минимизировать количество спичек? И как многие догадались, это конечно же квадрат. Но не все так просто, там нужно упростить эту идею.
Если взглянуть на рисунок выше, то можно заметить что наиболее выгодным положением для нового квадрата будет то у которого больше соседей, и при оптимальном случае — это будет 2 соседа.
То есть оптимальным случаем будет строить так:
Мы можем легко сказать куда надо строить следующий кубик если будет это делать руками, но как об этом сказать компьютеру?
Если взять листочек и начать строить некую плоскость из квадратиком что бы минимизировать количество ребер, мы заметим как мы строим:
Первоначально это был квадратик 1х1 — 1 квадрат, дальше удлиняем на до 2х1 — 2 квадрата, дальше:
2х2 — 3 и потом 4 квадрата
3х2 — 5 и 6 квадратов
3х3 — 7,8,9 квадратов
Внимательно посмотрим и видим закономерность: мы имеем плоскость A x B чтобы минимизировать количество ребер, следующие для построения плоскости будут (A+1) x B и потом (A+1) x (B + 1), последняя является квадратом, так как мы начинаем строить из 1 х 1
Напишем таблицу для массива DP:
| N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Размер | 1 x 1 | 2 x 1 | 2 x 2 | 2 x 2 | 3 x 2 | 3 x 2 | 3 x 3 | 3 x 3 | 3 x 3 |
| DP | 4 | 3 | 3 | 2 | 3 | 2 | 3 | 2 | 2 |
Анализируем таблицу:
для DP[1]=4
дальше когда мы добавляем новый ряд мы делаем новый квадрат используя 3 спички и до конца ряда достраиваем квадраты по 2 спички. Еще не чего не напоминает? Вспомним случай с 1D — первый квадрат 4 спички, остальные по 3, в данном случае это тот же дополнительный ряд, но с начальным квадратом в 3 спички и остальными в 2 спички.
| N для 2D | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| N для 1D | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | 3 |
| Размер | 1 x 1 | 2 x 1 | 2 x 2 | 2 x 2 | 3 x 2 | 3 x 2 | 3 x 3 | 3 x 3 | 3 x 3 |
| DP | 4 | 3 | 3 | 2 | 3 | 2 | 3 | 2 | 2 |
Теперь алгоритм решения:
DP[1]=4
A=1
B=1 // A x B плоскость
теперь нужно проходить от 1 до N и в это же время увеличивать A и B как я писал выше а также еще проходить по массиву DP но для 1D случая начиная сначала при каждом изменении A и B и идти до наибольшего из них:
j=1 // счетчик для DPfor1D, к тому же не забываем что теперь DPfor1D={3,2,2,2,2,2,2,2,...}
for i = 2 -> N
begin
if A*B<i
then begin
(A<B)?A++:B++
j=1
end
DP[i]:= DP[i-1]+DPfor1D[j]
j++
end
или так:
Result:= 4
newN:= 1
A:= 2
B:= 1
while newN <= N
begin
Result:= Result + 1D(min(A,B)) // 1D(N):=3+(N-1)*2 если N >= 1, иначе 0
(A<B)?A++:B++
newN=A*B
end
(A>B)?A--:B--
Result:= Result+ 1D(N-A*B)
И формула:
Result(N):=4+3*(количество полных квадратов которые есть до числа N без 1 + дополнительные числа которые идут перед полными квадратами)+2*(все остальное)
NSQRT:= int(sqrt(N))-1
NADD:= NSQRT + 1(если N <= NSQRT*(NSQRT+1))
Result(N):=4+3*(NSQRT+NADD)+2*(N-NSQRT-NADD)
3D
Вот добрались и до 3Д случая
В трехмерном случае, для минимализации количества спичек для построения, теперь уже, кубов нужно стремится к построению большого куба, но в промежуточных вариантах это будет:
A x B x C -> (A+1) x B x C -> (A+1) x (B+1) x C -> (A+1) x (B+1) x (C+1)
алгоритм решения будет таким же как и в 2D случае, но учитывая некоторые новые особенности:
1D(N):= 5+(N-1)*3
2D(N):= алгоритм приведенный выше в подразделе, но с корректировкой — 2D(1):= 8
3D(N):= алгоритм приведенный выше в 2D случае, но с учетом трехмерности — 3D(1):= 12, и при увеличение координат мы будем изменять результат так: Result:= Result + 2D(A*B*C/max(A,B,C)), т.е. нужно будет получать 2D от размера добавленной плоскости изменением параметром нашего нового параллелепипеда
И формула для 3D
Формула будет состоять из тех же частей что и формула для 2D, но также мы будет учитывать не только полные квадраты но и полные Кубы
Result(N):=12+8*(3*Nполные кубы+(0 или 1 или 2 в зависимости от N))+5*(2*Nполные квадраты+(0 или 1 в зависимости от N))+3*Nостальное
Но, к сожалению, эта формула не совсем правильна и требует большего умственного усилия для продумывания некоторых исключений и поправок.
Мысли на счет n-мерного случая
В предыдущих разделах мы исследовали от чего зависит минимализация спичек для для куба/квадрата и опираясь на это мы можем сделать алгоритм любого измерения:
Нужно учитывать со скольких спичек состоит первоначальный N-мерный квадрат, и просчитать какое количество спичек нужно чтобы достраивать новые элементы
Алгоритм увлечения размерности объекта мы вывели — на каждой итерации увеличивать на 1 наименьшую размерность.
Также поняли что при изменении размера объекта к результату нужно прибавлять значение функции (N-1)-го измерения от размера добавленной плоскости
В при создании формулы нужно учитывать количество чисел в N степени, N-1, N-2 и т.д. + учитывать особенности
Ссылки
E-olimp — Интернет-портал организационно-методического обеспечения дистанционных олимпиад по программированию для одаренной молодежи учебных заведений Украины.
Задача на портале, которую можете попробовать сдать — нужна регистрация
Статья о динамическом программировании
