Бюст с връщане

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

Упражнения

A: Настройки на Queens - 3

Решете обичайния проблем за поставяне на дами на n×n дъска при ограниченията n≤13. Използвайте схемата за обратно проследяване с груба сила с прекъсване на невъзможни ходове.

B: Товароносимост

Товароносимост \(M\) кг. Има \(n\) кутии с товари, масата на \(i\)та кутия е равна на \(m_i\). Определете коя е най-голямата маса стоки, които могат да бъдат отнесени с кола.

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

Програмата трябва да изведе едно число: максималното тегло, което може да се вземе с кола. Изведете число с точност до 15 цифри.

C: Проблемът с пътуващия търговец

На равнината са дадени \(N\) точки. Свържете ги със затворена полилиния с минимална дължина.

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

Отпечатайте едно реално число: минималната дължина на затворена полилиния, минаваща през всички тези точки. Отпечатайте отговора си с точност до 15 знака.

D: Товароносимост - 2

Решете задача B в ограниченията n≤27;. Използвайте следните оптимизации:

  1. Сортирайте теглата в низходящ ред. Търсенето започва с по-тежки товари, като първо обмисляме опцията, когато се вземе следващият товар.
  2. Прекъсване се прави, ако общата маса на всички взети стоки надвишава капацитета на превозното средство.
  3. Прекъсване се прави, ако общата маса на всички взети товари и всички останали товари е по-малка от най-добрия вече намерен резултат (т.е. ако резултатът не може да бъде подобрен със сигурност).
  4. За бързоза определяне на общата маса на всички останали стоки се използва предварително изчисление.

E: Проблем с пътуващия търговец - 2

Решете задача C с n≤12 ограничения. Използвайте следната оптимизация:

  1. Прекъсване, ако общата дължина на текущия маршрут е по-голяма или равна на най-известния затворен маршрут (т.е. със сигурност не е възможно да се подобри резултатът).

F: Равенство

Даден е израз: \[a_1 ? a_2 ? . ? a_n = S\]

Пребройте по колко начина в този израз можете да замените въпросителните знаци със знаците на операциите събиране и умножение, така че да се спазва равенството.

Програмата получава числото n (n≤26) и S (1≤S≤10 6 ) като вход. Следват n естествени числа ai, които също не надвишават 10 6 .

Отпечатайте едно число — броя на подредбите на знаците за събиране и умножение, които дават правилното равенство.