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

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

def Перебор(Ситуация):
    if Ситуация конечная:
        Завершающая обработка
    else:
        for Действие in Множество всех возможных действий:
            Применить Действие к Ситуация
            Перебор(Ситуация)
            откатить Действие назад

Упражнения

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

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

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

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

10
4
1
3
5
8

9.0

1073.15936137
5
359.840622077
640.476657457
63.7703847126
345.949354785
635.448660233

1064.0876642465998

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

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

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

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

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

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

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

4
0 0
1 0
1 1
2 1

4.82842712474619

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

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

E: Задача коммивояжера - 3

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

F: Равенство

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

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

Программа получает на вход число n и S. Далее идет n натуральных чисел a_i.

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

2 4
2 2

2

G: Монетки

В Волшебной стране используются монетки достоинством A₁, A₂,…, A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Сначала вводится число N (1≤N≤10⁹), затем —число M (1≤M≤10) и далее M попарно различных чисел A₁, A₂,…, A_M (1≤A_i≤10⁹).

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

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

5 2
1 2

3
2 2 1

7 2
1 2

-1

5 2
3 4

0

H: Пятнашки

Головоломка “игра в пятнашки” состоит из 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

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

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

J: Кабинет министров

Премьер-министр некоторого государства хочет составить новый кабинет министров. К составу нового кабинета есть следующие пожелания:

1. Министров должно быть как можно меньше (так ими легче управлять, да и на зарплате можно сэкономить);
2. Для каждой области государственной деятельности (строительство, финансы, внешняя политика и т.д.) должен быть хотя бы один министр, который в ней разбирается.

На рассмотрение Премьер-министра поступило N кандидатур. Определите, сколько и каких людей должны получить министерские посты, с учетом пожеланий.

Cначала вводится число N (натуральное, не превышает 10) — количество кандидатов в списке, затем вводится число K (натуральное, не превышает 20) – общее количество областей, в которых министры должны разбираться. Затем идет N строк следующего формата: в начале строки вводится число P_i (натуральное, не превышает K) – количество областей, в которых разбирается i-й кандидат, потом вводятся номера этих областей (натуральные числа, не превышают K).

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

3 2
2 1 2
2 1 2
2 1 2

1
1

4 3
1 1
1 2
1 3
2 1 2

2
3 4