Перебор с возвратом

Во всех задачах этого листка необходимо реализовать перебор с возвратом. Общая схема перебора с возратом такая:

алг Перебор (Ситуация)
нач
    если Ситуация конечная
    то
        Завершающая обработка
    иначе
        нц для любого возможного действия
            Применить действие к Ситуация
            Вызвать алгоритм Перебор(Ситуация)
            откатить действие назад
        кц
    все
кон

Упражнения

A: Грузоподъемность

Грузоподъемность машины \(M\) килограмм. Есть \(n\) ящиков с грузами, масса \(i\)-го ящика равна \(m_i\). Определите, какую наибольшую массу грузов можно увезти на автомашине.

Программа получает на вход действительное число \(M\), затем количество ящиков \(n\le 20\), затем \(n\) действительных чисел — массы ящиков.

Программа должна вывести единственное число — максимальную массу, которую можно увезти на машине. Выводите число с точностью в 15 знаков.

10
4
1 3 5 8

9

1073.15936137
5
359.840622077
640.476657457
63.7703847126
345.949354785
635.448660233

1064.0876642466

B: Задача коммивояжера

На плоскости даны \(n\) точек. Соедините их замкнутой ломаной линией минимальной длины.

Программа получает на вход число \(n\le10\). Далее идет \(n\) пар действительных чисел: координаты точек.

Выведите одно действительное число: минимальную длину замкнутой ломаной, проходящей через все эти точки. Ответ выводите с точностью в 15 знаков.

4
0 0
1 0
1 1
2 1

4.82842712474619

C: Грузоподъемность - 2

Решите задачу “Грузоподъемность“ в ограничениях \(n\le 27\). Используйте следующие оптимизации:

1. Отсортировать массы грузов по убыванию. Перебор начинать с более тяжелых грузов, сначала рассматриваем вариант, когда очередной груз берется.
2. Делается отсечение, если суммарная масса всех взятых грузов превышает вместимость машины.
3. Делается отсечение, если суммарная масса всех взятых грузов и всех оставшихся грузов меньше наилучшего уже найденного результата (т.е. если заведомо не удастся улучшить результат).
4. Для быстрого определения суммарной массы всех оставшихся грузов используется предподсчет.

D: Задача коммивояжера - 2

Решите задачу коммивояжера в ограничениях \(n\le 12\). Используйте следующую оптимизацию:

1. Делать отсечение, если суммарная длина текущего маршрута больше или равна наилучшему известному замкнутому маршруту (т.е. заведомо не удастся улучшить результат).

E: Равенство

Дано выражение: \[a_1 ? a_2 ? ... ? a_n = S\]

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

Программа получает на вход число \(n\) (\(n\le 26\)) и \(S\) (\(1\le S\le10^6\)). Далее идет \(n\) натуральных чисел \(a_i\), также не превосходящих \(10^6\).

Выведите одно число — количество расстановок знаков сложения и умножения, дающих верное равенство.

2 4
2 2

2

F: Монетки

В Волшебной стране используются монетки достоинством \(a_1\), \(a_2\), ..., \(a_m\). Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму \(S\). Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Сначала вводится число \(S\) (\(1\le S\le 10^9\)), затем число \(m\) (\(1\le m\le 15\)) и далее \(m\) попарно различных чисел \(a_1\), \(a_2\), ..., \(a_m\) (\(1\le a_i\le 10^9\)).

Выведите сначала \(k\) — количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите \(k\) чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число –1 (минус один).

5 2
1 2

3
2 2 1

7 2
1 2

-1

5 2
3 4

0

G: Пятнашки

Головоломка “игра в пятнашки” состоит из 15 квадратиков, уложенные в рамку размером 4×4, при этом одно место остается незанятым. За один ход можно передвинуть один квадратик, соседний с незанятым местом, в незанятое место. Цель головоломки: упорядочить квадратики до такого положения:

Вам дана некоторое начальное положение головоломки. Известно, что ее можно решить не более, чем за 20 ходов. Найдите решение этой головоломки.

Программа получает на вход 4 строки, содержащие по 4 числа: значения, записанные на квадратиках в начальном расположение. Число 0 соответствует пустой клетке.

Программа должна вывести последовательность перемещений, решающих головоломку в виде строки из букв L, R, U, D решающую головоломку, где буква L соответствует движению квадратика с числом влево, R — вправо, U — вверх, D — вниз.

 1  2  3  4
 5  6  7  8
 9 10 15 11
13 14  0 12

DLU

H: Пятнашки - 2

В условиях предыдущей задачи найдите и выведите кратчайшее решение (т.е. решение содержащее наименьшее число перемещений). Гарантируется, что входные данные допускают решение головоломки не более чем за 20 перемещений.