Бюст с връщане
Във всички задачи от този работен лист е необходимо да се приложи итерация с обратно проследяване. Общата итерационна схема с връщане е следната:
Упражнения
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;. Използвайте следните оптимизации:
- Сортирайте теглата в низходящ ред. Търсенето започва с по-тежки товари, като първо обмисляме опцията, когато се вземе следващият товар.
- Прекъсване се прави, ако общата маса на всички взети стоки надвишава капацитета на превозното средство.
- Прекъсване се прави, ако общата маса на всички взети товари и всички останали товари е по-малка от най-добрия вече намерен резултат (т.е. ако резултатът не може да бъде подобрен със сигурност).
- За бързоза определяне на общата маса на всички останали стоки се използва предварително изчисление.
E: Проблем с пътуващия търговец - 2
Решете задача C с n≤12 ограничения. Използвайте следната оптимизация:
- Прекъсване, ако общата дължина на текущия маршрут е по-голяма или равна на най-известния затворен маршрут (т.е. със сигурност не е възможно да се подобри резултатът).
F: Равенство
Даден е израз: \[a_1 ? a_2 ? . ? a_n = S\]
Пребройте по колко начина в този израз можете да замените въпросителните знаци със знаците на операциите събиране и умножение, така че да се спазва равенството.
Програмата получава числото n (n≤26) и S (1≤S≤10 6 ) като вход. Следват n естествени числа ai, които също не надвишават 10 6 .
Отпечатайте едно число — броя на подредбите на знаците за събиране и умножение, които дават правилното равенство.