Динамическое программирование в поиске чисел

#алгоритм #любой_язык #динамическое_программирование

На всех n-значных числах нужно посчитать кол-во таких чисел у которых любые две соседние
цифры имеют разность по модулю <= 1 
Допустим есть функция f(n) = кол-ву этих чисел 
Если для f(1) = 0, таких нет, для f(2) таких 8*3+2 (т.к. на промежутке 10-99 на всех
десятках есть по 3 таких числа, кроме числа начинающегося с 9 там их 2 т.к. оно крайнее,
например 10,11,12,21,22,23,32,33,34 ... 98,99.)
Получается что f(n) = f(n-1)*10 (т.к. если к изначально подходящему числу подставить
в конец любую цифру, то оно все равно удовлетворяет условию) + ..что то еще..
Долго не могу сложить этот пазл, как посчитать кол-во следующих n
    

Ответы

Ответ 1

Заполняем табличку. F - количество чисел длиной N, заканчивающихся цифрой L:

  F(N, L) {L=1..8} = F(N-1, L-1) + F(N-1, L) + F(N-1, L+1)
  F(N, 0) = F(N-1, 0) + F(N-1, 1)
  F(N, 9) = F(N-1, 9) + F(N-1, 8)
  F(1, 0) = 0
  F(1, K>0) = 1

Комбинаторная задача на перестановки

#алгоритм #оптимизация #комбинаторика #динамическое_программирование

Есть 3 числа: A, B и C. Необходимо получить выражение A+B=C, при этом чтоб C было
минимальным. Нужно переставлять биты внутри чисел (переставлять можно только в пределах
одного числа. Т.е можно поменять какие-то 2 бита внутри числа А, но нельзя поменять
два бита из А и B).

Ограничения на числа 2^31-1.

Решения может не существовать, все числа положительные.

Ну перебором тут не выйдет. Пробовал генетический алгоритм, в некоторых случаях он
работает, но, к сожалению, не во всех. Возможно задача решается способами динамического
программирования или программированием по профилю, но не особо понимаю, как должна
выглядеть динамика.

Подскажите в какую сторону копать.
    

Ответы

Ответ 1

Пишу только алгоритм, автору думаю будет интересно самому реализовать.

1 - Перебираем число С (если делать правильно, то будет не больше 30 млн вариантов,
С[31,15] ). В порядке возрастания. 

Теперь проверим можно ли получить фиксированное С.

Для этого используем динамику. 

Начальное значение F[0][ bit_count(A)] [bit_count(B)][0] = true;

Поля: {бит в С, осталось битов в А, осталось битов в Б, есть перенос бита}.

Значение - можно ли такое получить.

Пересчёт. Если в С бит {i} совпадает с переносом, то переходы либо два нуля или 2
едиинцы {(a-1, b-1), (a,b)} флаг переноса выставить в первом случае. Аналогично если
не совпадают { (a-1,b), (a,b-1) } флаг переноса не меняется.

Если F[32][0][0][0] = true то мы нашли что хотели. Восстановить ответ можно и не
сложно (в крайнем случае ещё раз эту же динамику запустить).

Сложность порядка оценить тяжело, оценка сверху 30кк*32*32 но она очень грубая. В
целом должно успеть (делать отсечение по отрицательному количеству не забывать).

Задача про паркет

#алгоритм #комбинаторика #динамическое_программирование

Есть поле из клеток, размеры которого [n * m]. Необходимо покрыть это поле плитками
размера [1 * 2] (их можно поворачивать) таким образом, чтоб все клетки поля были накрыты,
и чтоб плитки не вылазили за границы поля. Задача состоит в том, чтоб найти количество
таких покрытий.

Данную задачу я решил с помощью динамики по профилю. Профиль - состояние одного столбца
поля. Подразумевается, что слева от данного профиля уже все клетки заполнены, а справа
ещё нет. Переход из профиля в профиль существует, если можно корректно положить некоторое
количество плиток (переходы хранятся в матрице dp).

Затем я считаю матрицу ответов:

if (dp[j][i]) ans[k][i] += ans[k - 1][j];


И после посчитанной матрицы ответов считаю ответ на задачу

if (isFinishing(i)) res += ans[m - 1][i];

Эта строчка означает, что если профиль может являться завершающим, то добавить это
число в ответу.

Данное решение вполне себе работает. Но затем я нашел модификацию данной задачи.
Модификация состоит в том, чтобы найти количество таких покрытий, в которых не будет
сплошных линий из плиток [1 * 2].

Пример: 

Первая картинка - это пример того, какими должны быть покрытия, вторая - какими не
должны. 

У меня был вариант хранить в динамике ещё состояние для каждой строки, была ли она
перекрыта хоть раз вертикальной плиткой, и добавлять к ответу только эти варианты.
Возможно, это бы и работало, но я не особо понимаю, как это реализовать. 

Подскажите, как реализовать, или предложите свои варианты решения.
    

Ответы

Ответ 1

Можно сделать динамически по рядам длины n. Для каждого промежуточного решения хранить
состояние "дырок", куда можно подставить вертикальные плитки. Установим, что мы всегда
движемся сверху вниз, значит дырки будут внизу. Динамический массив будет иметь вид: 

[int ряды, bool[] дырки] = кол-во решений


Например, все возможные решения для 1 ряда длиной 4:

[1, [0, 0, 1, 1]] = 1 // [xx] . .
[1, [1, 0, 0, 1]] = 1 // . [xx] .
[1, [1, 1, 0, 0]] = 1 // . . [xx]
[1, [1, 1, 1, 1]] = 1 // . .  . .


0 - горизонтальная плитка, 1 - пустое место для будущей вертикальной плитки. Количество
нулей идущих подряд всегда должно быть парным, все нули запрещены (что бы удовлетворить
ваше условие).

Дальше мы пытаемся соединить решение для x-1 рядов с решением для 1 ряда, что бы
получить решение для x рядов:

for (prev in solutions[x-1])
for (single in solutions[1])
{
    if (дырки prev совместимы c дырками single)
    {
        holes = считаем как будут выглядеть дырки после совмещения 2 решений
        solutions[x][holes] += prev;
    }
}


Конечным решением будет значение solutions[m, [0, 0, 0, 0, ... 0]], где все нули
- это полностью заполненный последний ряд.

Возможно существует более элегантное решение.

Комбинаторная задача на перестановки

Есть 3 числа: A, B и C. Необходимо получить выражение A+B=C, при этом чтоб C было минимальным. Нужно переставлять биты внутри чисел (переставлять можно только в пределах одного числа. Т.е можно поменять какие-то 2 бита внутри числа А, но нельзя поменять два бита из А и B).
Ограничения на числа 2^31-1.
Решения может не существовать, все числа положительные.
Ну перебором тут не выйдет. Пробовал генетический алгоритм, в некоторых случаях он работает, но, к сожалению, не во всех. Возможно задача решается способами динамического программирования или программированием по профилю, но не особо понимаю, как должна выглядеть динамика.
Подскажите в какую сторону копать.

Ответ

Пишу только алгоритм, автору думаю будет интересно самому реализовать.
1 - Перебираем число С (если делать правильно, то будет не больше 30 млн вариантов, С[31,15] ). В порядке возрастания.
Теперь проверим можно ли получить фиксированное С.
Для этого используем динамику.
Начальное значение F[0][ bit_count(A)] [bit_count(B)][0] = true
Поля: {бит в С, осталось битов в А, осталось битов в Б, есть перенос бита}.
Значение - можно ли такое получить.
Пересчёт. Если в С бит {i} совпадает с переносом, то переходы либо два нуля или 2 едиинцы {(a-1, b-1), (a,b)} флаг переноса выставить в первом случае. Аналогично если не совпадают { (a-1,b), (a,b-1) } флаг переноса не меняется.
Если F[32][0][0][0] = true то мы нашли что хотели. Восстановить ответ можно и не сложно (в крайнем случае ещё раз эту же динамику запустить).
Сложность порядка оценить тяжело, оценка сверху 30кк*32*32 но она очень грубая. В целом должно успеть (делать отсечение по отрицательному количеству не забывать).

Запись числа как суммы треугольных чисел

Попалась новогодняя задачка - записать число 2018 как сумму разных треугольных чисел
Вообще-то, не так чтобы сложно, на бумажке решить можно, но там было приведено общее количество таких записей. Как их посчитали? Таких чисел, меньших 2018 - аж 63, так что перебором - вряд ли.
Мне все покоя не дает не дающееся мне динамическое программирование - им тут можно как-то добраться до ответа?
Если кто сомневается - это задание не учебное :)

Ответ

Второй раз наталкиваюсь на задачу, которую можно решить длинно, а можно очень быстро... :) Первый ответ опять не убираю, но настоящее решение - в части Update...
Тут недавно спрашивали о переборе с возвратом :) - это почти оно самое. Кстати, с применением рекурсии для упрощения.
Итак, решение может включать некоторое треугольное число, может не включать. В любом случае задача сводится к поиску решений для либо того же числа (если не включаем) или меньшего на включенное треугольное число - но уже для меньшего множества треугольных чисел. Получается рекурсия не глубже 64, но на каждом уровне - ветвящаяся. Но так как отбрасывается очень много вариантов - то посчитать реально, у меня на машине - за примерно 9.5 секунд.
#include #include
using namespace std;
vector tri; // Запас треугольных чисел :) long long total = 0; // Количество решений
vector solution; // Вектор для решения
// Рекурсивный вызов, изначально - доступны все числа (k) void getThree(int n, int k = tri.size()-1) { if (n==0) // Ура, найден! { ++total; // Если захотим вывести - раскомментировать // for(auto i: solution) cout << i << " "; cout << endl; return; }
if (n < 0 || k < 0) return; // Тупик - решение не получилось
// Ветвь с использованием k-го числа solution.push_back(tri[k]); getThree(n-tri[k],k-1); solution.pop_back();
// Ветвь без него getThree(n,k-1); }
int main(int argc, const char * argv[]) { // Заполняем массив треугольными числами for(int i = 1; i <= 64; ++i) tri.push_back(i*(i-1)/2);
// Приступаем... getThree(2018); cout << total << endl; }
На ideone времени не хватает :(
У меня выходит 2693210 вариантов (P.S. так что с long long я явно пожадничал :))
Может, есть какой алгоритм побыстрее - не знаю, но готов поверить :)
Update
Есть и побыстрее, и именно динамическим программированием!
Итак, просто создаем массив
long long res[2019][65];
в котором изначально все элементы - -1, и который указывает количество способов записать число n треугольными числами на выше k-го в ячейке res[n][k]
наша основная формула остается та же, что и ранее -
getThree(n-tri[k],k-1) + getThree(n,k-1)
только теперь мы используем memoization и записываем ответы в массив.
Т.е. функция приобретает вид
long long getThree(int n, int k = tri.size()-1) { if (n < 0 || k < 0) return 0; // Не вышло if (k == 0) // Годится как вариант n==1, так и n==0 { if (n == tri[k]) res[n][k] = 1; if (n == 0) res[n][k] = 1; } else if (n == 0) res[n][k] = 1;
if (res[n][k] == -1) // Если мы еще не рассчитывали это значение - { // считаем и сохраняем res[n][k] = getThree(n-tri[k],k-1) + getThree(n,k-1); } return res[n][k]; }
Такой код позволяет мгновенно получить тот же результат - 2693210.
А вот почему я оставил long long: если позволить выбирать значения повторно (ну, типа, 9 можно писать и как 6+3, и как 3+3+3), то чтобы получить это количество, достаточно просто заменить
getThree(n-tri[k],k-1)
на
getThree(n-tri[k],k)
(т.е. можно использовать то же число повторно). Результат получается тоже весьма быстро, только он куда побольше, так что перебором с отсечением уже не обойтись: 32090936486947985
А неплохая задачка :)

Задача про паркет

Есть поле из клеток, размеры которого [n * m]. Необходимо покрыть это поле плитками размера [1 * 2] (их можно поворачивать) таким образом, чтоб все клетки поля были накрыты, и чтоб плитки не вылазили за границы поля. Задача состоит в том, чтоб найти количество таких покрытий.
Данную задачу я решил с помощью динамики по профилю. Профиль - состояние одного столбца поля. Подразумевается, что слева от данного профиля уже все клетки заполнены, а справа ещё нет. Переход из профиля в профиль существует, если можно корректно положить некоторое количество плиток (переходы хранятся в матрице dp).
Затем я считаю матрицу ответов:
if (dp[j][i]) ans[k][i] += ans[k - 1][j];
И после посчитанной матрицы ответов считаю ответ на задачу
if (isFinishing(i)) res += ans[m - 1][i];
Эта строчка означает, что если профиль может являться завершающим, то добавить это число в ответу.
Данное решение вполне себе работает. Но затем я нашел модификацию данной задачи. Модификация состоит в том, чтобы найти количество таких покрытий, в которых не будет сплошных линий из плиток [1 * 2].
Пример:
Первая картинка - это пример того, какими должны быть покрытия, вторая - какими не должны.
У меня был вариант хранить в динамике ещё состояние для каждой строки, была ли она перекрыта хоть раз вертикальной плиткой, и добавлять к ответу только эти варианты. Возможно, это бы и работало, но я не особо понимаю, как это реализовать.
Подскажите, как реализовать, или предложите свои варианты решения.

Ответ

Можно сделать динамически по рядам длины n. Для каждого промежуточного решения хранить состояние "дырок", куда можно подставить вертикальные плитки. Установим, что мы всегда движемся сверху вниз, значит дырки будут внизу. Динамический массив будет иметь вид:
[int ряды, bool[] дырки] = кол-во решений
Например, все возможные решения для 1 ряда длиной 4:
[1, [0, 0, 1, 1]] = 1 // [xx] . . [1, [1, 0, 0, 1]] = 1 // . [xx] . [1, [1, 1, 0, 0]] = 1 // . . [xx] [1, [1, 1, 1, 1]] = 1 // . . . .
0 - горизонтальная плитка, 1 - пустое место для будущей вертикальной плитки. Количество нулей идущих подряд всегда должно быть парным, все нули запрещены (что бы удовлетворить ваше условие).
Дальше мы пытаемся соединить решение для x-1 рядов с решением для 1 ряда, что бы получить решение для x рядов:
for (prev in solutions[x-1]) for (single in solutions[1]) { if (дырки prev совместимы c дырками single) { holes = считаем как будут выглядеть дырки после совмещения 2 решений solutions[x][holes] += prev; } }
Конечным решением будет значение solutions[m, [0, 0, 0, 0, ... 0]], где все нули - это полностью заполненный последний ряд.
Возможно существует более элегантное решение.