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

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

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 натуральных чисел ai.

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

Ввод Вывод 
2 4
2 2
 
2