Несколько слов об этом методе. Что значит динамическое и еще программирование? Можно подумать, что нужно как то по новому программировать. На самом деле необходимо просто расписать решение задачи на каждом шаге и получить некоторую рекуррентную зависимость от предыдущего шага, при этом можно рассматривать не все варианты, а только те, которые не совпадают на предыдущем шаге или имеют симметричные значения.
Рассмотрим следующую задачу: даны N монет с указанием достоинств. Определить, можно ли распределить их на две кучки с наименьшим разрывом между ними. Например, для N=4 даны 4, 3, 7, 2. Тогда их можно распределить на две кучки так:
1 шаг: 4 - 0 -> разность =4
2 шаг: 4+3- 0 -> разность =7
или 4 - 3 -> разность =1
3 шаг: 4+3+7 - 0 -> разность=14
или 4+3 - 7 -> разность=0
или 4+7 - 3 -> разность =8
или 4 - 3+7 -> разность =-6
3 шаг: 4+3+7+2 - 0 -> разность =16
или 4+2 - 3+7 -> разность =-4
или 4+3+7 - 2 -> разность =12
или 4 - 3+7+2 -> разность =-8
Итак, получим решение 4, 3, 2 в первой кучке и 7 во второй или 4,3/7, 2 с минимальным разрывом в 2.
Я привела все варианты, но если посмотреть внимательно, то можно заметить, что хранить все варианты нет необходимости, можно запомнить на каждом шаге разность и знак + или - для текущей монеты: + положили в первую кучку, - во вторую.
1 шаг: 4 - 0 -> разность =4
2 шаг: 4+3- 0 -> разность =4+3=7
или 4 - 3 -> разность =4-3=1
3 шаг: 4+3+7 - 0 -> разность =7+7=14
или 4+3 - 7 -> разность =7-7=0
или 4+7 - 3 -> разность =1+7=8
или 4 - 3+7 -> разность = 1-7=-6
3 шаг: 4+3+7+2 - 0 -> разность =14+2=16
или 4+2 - 3+7 -> разность = -6+2=-4
или 4+3+7 - 2 -> разность =14-2=12
или 4 - 3+7+2 -> разность =-6-2=-8
Но может быть решение найдено, если начинать с другой монеты. Будем рассматривать все такие варианты, но искать при этом каждый раз минимум среди разностей по модулю. Хранить будем в массиве +1 или -1 в зависимости от полученного минимума. На следующем шаге используем разность без модуля.
Представим получаемые разности в виде таблицы:
Полученное значение в последнем столбце сравниваем с предыдущим минимумом и если оно равно 0, то решение найдено, иначе ищем минимум по модулю. В примере это MIN(-4,-4,2,-6)=2.
Пусть исходные значения хранятся в массиве В:=(4, 3, 7, 2). Результаты вычислений храним в двумерном массиве A(4,4). Тогда алгоритм вычисления запишем в виде функции:
R=B(i)
+1, если i=j; R не изменяется
A(i,j)= если i<>j +1, если |R+B(j)|<=|R-B(j)|; R=R+B(j)
-1, если |R-B(j)|<|R+B(j)|; R=R-B(j)
Для каждого i-го решения после вычисления всех значений i-ой строки находим Rmin = MIN ( Rmin, |R|). При этом запоминаем номер строки Imin для дальнейшего вывода. Rmin в начале можно присвоить сумме всех значений массива B(j).
При выводе если A(Imin,J)=+1, то B(J) в первую кучку, если -1 - во вторую.
Итак, мы разобрали задачу с элементами динамического программирования. Попробуйте написать программу самостоятельно. Для таблицы можно использовать логические значения TRUE (+1) и FALSE (-1). Можно не использовать всю таблицу, а только два двумерных массива: один хранит значения на текущем шаге, другой - значения с минимумом.
Иногда при подборе такого решения нужно доказывать состоятельность выбранного пути решения. Не факт, что при таком выборе пути мы найдем верное решение или оно будет не лучшим из всех возможных. Поэтому иногда приходится выполнять полный перебор решений. Но это видно сразу из заданных диапазонов и времени выполнения: обычно это или время завышено или диапазон при малом времени выполнении слишком мал.
Вот выдержки с сайта acmp.ru по этому вопросу:
Пусть есть 7 чисел:
Рассчитаем разности по модулю по парам:
и через один утроенные разности по модулю:
Рассмотрим следующую задачу: даны N монет с указанием достоинств. Определить, можно ли распределить их на две кучки с наименьшим разрывом между ними. Например, для N=4 даны 4, 3, 7, 2. Тогда их можно распределить на две кучки так:
1 шаг: 4 - 0 -> разность =4
2 шаг: 4+3- 0 -> разность =7
или 4 - 3 -> разность =1
3 шаг: 4+3+7 - 0 -> разность=14
или 4+3 - 7 -> разность=0
или 4+7 - 3 -> разность =8
или 4 - 3+7 -> разность =-6
3 шаг: 4+3+7+2 - 0 -> разность =16
или 4+3+2 - 7 -> разность =2
или 4+7+2 - 3 -> разность =10или 4+2 - 3+7 -> разность =-4
или 4+3+7 - 2 -> разность =12
или 4+3 - 7+2 -> разность =-2
или 4+7 - 3+2 -> разность =6или 4 - 3+7+2 -> разность =-8
Итак, получим решение 4, 3, 2 в первой кучке и 7 во второй или 4,3/7, 2 с минимальным разрывом в 2.
Я привела все варианты, но если посмотреть внимательно, то можно заметить, что хранить все варианты нет необходимости, можно запомнить на каждом шаге разность и знак + или - для текущей монеты: + положили в первую кучку, - во вторую.
1 шаг: 4 - 0 -> разность =4
2 шаг: 4+3- 0 -> разность =4+3=7
или 4 - 3 -> разность =4-3=1
3 шаг: 4+3+7 - 0 -> разность =7+7=14
или 4+3 - 7 -> разность =7-7=0
или 4+7 - 3 -> разность =1+7=8
или 4 - 3+7 -> разность = 1-7=-6
3 шаг: 4+3+7+2 - 0 -> разность =14+2=16
или 4+3+2 - 7 -> разность =0+2=2
или 4+7+2 - 3 -> разность =8+2=10или 4+2 - 3+7 -> разность = -6+2=-4
или 4+3+7 - 2 -> разность =14-2=12
или 4+3 - 7+2 -> разность =0-2=-2
или 4+7 - 3+2 -> разность =8-2=6или 4 - 3+7+2 -> разность =-6-2=-8
Но может быть решение найдено, если начинать с другой монеты. Будем рассматривать все такие варианты, но искать при этом каждый раз минимум среди разностей по модулю. Хранить будем в массиве +1 или -1 в зависимости от полученного минимума. На следующем шаге используем разность без модуля.
Представим получаемые разности в виде таблицы:
Начинаем с
|
4
|
3
|
7
|
2
|
4
|
4
|
MIN(4+3,4-3)=1
|
MIN(1+7,1-7)=-6
|
MIN(-6+2,-6-2)=-4
|
3
|
MIN(3+4,3-4) =-1
|
-1
|
MIN(-1+7,-1-7)=-6
|
MIN(-6+2,-6-2)=-4
|
7
|
MIN(7+4,7-4) =3
|
MIN(3+3,3-3)=0
|
0
|
MIN(0+2,0-2)=2
|
2
|
MIN(2+4,2-4) =-2
|
MIN(-2+3,-2-3)=1
|
MIN(1+7,1-7)=-6
|
-6
|
Пусть исходные значения хранятся в массиве В:=(4, 3, 7, 2). Результаты вычислений храним в двумерном массиве A(4,4). Тогда алгоритм вычисления запишем в виде функции:
R=B(i)
+1, если i=j; R не изменяется
A(i,j)= если i<>j +1, если |R+B(j)|<=|R-B(j)|; R=R+B(j)
-1, если |R-B(j)|<|R+B(j)|; R=R-B(j)
Для каждого i-го решения после вычисления всех значений i-ой строки находим Rmin = MIN ( Rmin, |R|). При этом запоминаем номер строки Imin для дальнейшего вывода. Rmin в начале можно присвоить сумме всех значений массива B(j).
При выводе если A(Imin,J)=+1, то B(J) в первую кучку, если -1 - во вторую.
Итак, мы разобрали задачу с элементами динамического программирования. Попробуйте написать программу самостоятельно. Для таблицы можно использовать логические значения TRUE (+1) и FALSE (-1). Можно не использовать всю таблицу, а только два двумерных массива: один хранит значения на текущем шаге, другой - значения с минимумом.
Иногда при подборе такого решения нужно доказывать состоятельность выбранного пути решения. Не факт, что при таком выборе пути мы найдем верное решение или оно будет не лучшим из всех возможных. Поэтому иногда приходится выполнять полный перебор решений. Но это видно сразу из заданных диапазонов и времени выполнения: обычно это или время завышено или диапазон при малом времени выполнении слишком мал.
Вот выдержки с сайта acmp.ru по этому вопросу:
Динамическое программирование (ДП) - метод решения задач путем составления последовательности из подзадач таким образом, что:
- первый элемент последовательности (возможно несколько элементов) имеет тривиальное решение
- последний элемент этой последовательности - это исходная задача
- каждая задача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами
Другими словами, для решения задачи T методом ДП составляется некоторая последовательность подзадач T1, T2, ... Tn такая, что решение задачи T1 уже имеет решение, T = Tn, и самое главное, что зная решения задач T1, T2, ... Ti-1 можно вывести решение задачи Ti для любого i = 2..n .
Доказательство работоспособности метода ДП напрямую следует из принципа математической индукции. Действительно, если нам удастся для некоторой задачи построить вышеупомянутую последовательность, удовлетворяющую данным свойствам, то зная T1 мы легко вычислим T2 (при i=2), а из решений задач T1 и T2 будет следовать решение задачи T3 (при i=3) и т.д. увеличивая значение i мы будем находить решение задачи Ti через ранее решенные задачи до тех пор, пока i не достигнет значения n, а решение задачи Tn эквивалентно решению исходной задачи.
Динамическое программирование обычно придерживается двух подходов к решению задач:
- Нисходящее ДП: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
- Восходящее ДП: Все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего ДП в смысле размера необходимого стэка и количества вызова функций, но иногда бывает нелегко заранее выяснить решение каких подзадач нам потребуется в дальнейшем.
Пусть есть 7 чисел:
| 1 | 5 | 2 | 3 | 9 | 1 | 10 |
| 4 | 3 | 1 | 6 | 8 | 9 |
| 3 | 6 | 21 | 6 | 3 |
Как здесь применить метод динамического программирования? Что нам дают эти разности? Если брать сразу min(4,3)=3, то дальше нужно перепрыгнуть и получим min(21,1)=1, а далее min(6,6)=6. Но какой брать минимум? Если через один, то сумма равна 3+1+6+3=13, а если подряд, то сумма равна 3+1+6+8+9=27.
Еще пример для 10 чисел:
| 3 | 4 | 8 | 10 | 1 | 7 | 1 | 10 | 12 | 15 |
| 1 | 4 | 2 | 9 | 6 | 6 | 9 | 2 | 3 | |
| 15 | 18 | 21 | 9 | 0 | 9 | 33 | 15 |
Min(1,15)=1, min(4,18)=4, min(2,21)=2, min(9,9)=9 и далее либо 6+6+9+2+3 либо 6+9+2+3. Как определить дальнейшие действия? Пока не дойдешь до конца не узнаешь. А если таких развилок несколько? Вроде намечается путь рекурсивного вызова с возвратом. Но есть другой способ.
Пусть мы "стоим" на 2-м элементе. Как можно придти в это положение? С какой суммой или "багажом"? Пока только одним способом: 4-3=1. Запомним это число в переменную Р[2]. Перейдем к 3-му элементу. К нему можно придти двумя способами: (8-3)*3=15 или (8-4)+P[2]=5. Среди этих двух чисел наименьшее 5. Запомним в Р[3].
Далее, для i=4 (10-8)+P[3]=7 или (10-4)*3+P[2]=19. P[4]=7.
Для i=5 (10-1)+P[4]=16 или (8-1)*3+P[3]=26. P[5]=16.
Для i=6 (7-1)+P[5]=24 или (10-7)*3+P[4]=16. P[6]=16.
Для i=7 (7-1)+P[6]=22 или (1-1)*3+P[5]=16. P[7]=16.
Для i=8 (10-1)+P[7]=25 или (10-7)*3+P[6]=25. P[8]=25.
Для i=9 (12-10)+P[8]=27 или (12-1)*3+P[7]=49. P[9]=27.
Для i=10 (15-12)+P[9]=30 или (15-10)*3+P[8]=40. P[10]=30.
Итак, запишем функцию для получения решения на каждом i-ом шаге:
P[2]=abs(A[2]-A[1]), P[3]=min(abs(A[3]-A[2]),abs(A[3]-A[1])*3),
P[i] = min (abs(A[i]-A[i-1])+P[i-1],abs(A[i]-A[i-2])*3)+P[i-2]), если i>2.
Осталось написать функцию минимума двух чисел и алгоритм готов.
Подумайте, как в этой задаче можно обойтись без массивов?
Удачи!
P[2]=abs(A[2]-A[1]), P[3]=min(abs(A[3]-A[2]),abs(A[3]-A[1])*3),
P[i] = min (abs(A[i]-A[i-1])+P[i-1],abs(A[i]-A[i-2])*3)+P[i-2]), если i>2.
Осталось написать функцию минимума двух чисел и алгоритм готов.
Подумайте, как в этой задаче можно обойтись без массивов?
Удачи!
Комментариев нет:
Отправить комментарий