нтів у безлічі з поля partys, тобто має сенс відразу підрахувати, в якій кількості партій полягає той чи інший житель. Тепер слід впорядкувати масив s за зменшенням значень поля number. Верхню оцінку для числа членів парламенту ( kmax ) підрахуємо, побудувавши наближене рішення даної задачі таким чином: по-перше, включимо до парламенту жителя, що складається в максимальній кількості партій, потім виключимо ці партії з інших множин і заново знайдемо в залишився масиві елемент з максимальним значенням поля number (вже перерахованого) і включимо його до парламенту, і так далі, до тих пір, поки сума значень перелічених полів number у жителів, включених до парламент, не дорівнюватиме n . Знайдене кількість членів парламенту і буде kmax .
Тепер слід розглядати поєднання з ( kmax - 1) елемента, потім з ( kmax - 2) і т. д. елементів. Якщо сполучень з якогось розглянутого кількості елементів k , рішення знайдено не буде, то це означає, що точним є рішення з кількістю членів парламенту k +1. Так як масив s впорядкований, то, якщо рішення для того чи іншого значення k існує, то, швидше за все, воно буде знайдено при розгляді в лексикографічному порядку перших же сполучень за k елементів. Тому тимчасова трудомісткість в переборі виникає, тільки якщо рішення c даними значенням k немає. У такій ситуації можна скористатися наступним "ненауковим" прийомом: на пошук рішення для кожного k , меншого, ніж kmax відведемо фіксовану кількість часу, скажімо, 2-3 секунди (точніше даний час стоїть визначити експериментальним шляхом). Якщо за відведений час рішення не знайдено, то слід вважати повний перебір неможливим і закінчити виконання програми. У будь-якому випадку, ми будемо мати якесь рішення вихідної задачі: точне або наближене, тобто, можливо, містить більше членів парламенту, ніж мінімально можливо. Однак, на практиці такий підхід майже завжди призводить до точного рішення, в силу перебору "з перевагою ", що проводиться для кожного k (неможливість проведення повного перебору для будь-якого k на практиці відповідає відсутності рішення для даного k ).
Приклад 2. Дан автобусний квиток з номером, що складається з N цифр. Розставити між цифрами знаки арифметичних операцій '+', '-', '*', '/' (Цілочисельне ділення) і дужки таким чином, щоб значення отриманого виразу було одно 100. Можна утворювати багатозначні числа з стоять поруч цифр. Вираз повинен бути коректним з точки зору арифметики. Допустимі зайві дужки, що не порушують коректності вираження. При обчисленнях використовується стандартний пріоритет операцій, число цифр N в номері квитка не більше 6. ( 5-а Всеросійська олімпіада з інформатики , м. Троїцьк, 1993 р.)
Рішення . для побудови універсального алгоритму розв'язання даної задачі будемо вважати злиття двох сусідніх цифр однією з операцій. Тоді між кожною парою сусідніх цифр може стояти одна з 5 операцій. Для N цифр отримуємо 5 N -1 різних варіантів розстановки операцій. Перебирати всі варіанти розстановки операцій найзручніше за допомогою розгляду всіх чисел у 5-річної системі числення, що складаються не більше ніж з N - 1 цифри, тобто для N = 6 від 00000 до 44444. Для перебору таких чисел необхідно написати процедуру збільшення 1 в 5-ричной системі числення. Для кожного з варіантів розстановки операцій перейдемо від вихідного масиву з N цифр квитка, до масиву з К чисел, де K = ( N - кількість операцій злиття цифр в розглянутому варіанті). Тепер ми повинні розглянути всі перестановки з K - 1 арифметичної операції в даному варіанті. Кожна перестановка відповідає одному з порядків виконання арифметичних операцій. Так, для 4-х чисел, перестановка номерів операцій 3, 1, 2 означає, що спочатку потрібно виконати арифметичну дію між 3-м і 4-м числом, потім між 1-м і 2-м і потім залишився. Якщо результат виконання дій даного варіанту в порядку, відповідному поточної перестановці, дорівнює шуканого числа 100, то задача вирішена і можна перейти до друку результату. Для даної задачі можливі й більш ефективні рішення, але в силу її слабкий розмірності, комбінаторний перебір виявляється цілком прийнятним.
Приклад 3 . Губернатор однієї з областей уклав з фірмою " HerNet " контракт на підключення всіх міст області до комп'ютерної мережі. Мережа створюється наступним чином: у області встановлюється декілька станцій супутникового зв'язку, і потім від кожного міста прокладається кабель до однієї із станцій. Технологія, використовувана підприємством вимагає при збільшенні відстані збільшення товщини кабелю. Таким чином, вартість кабелю, що з'єднує місто зі станцією, при використовуваної підприємством технології буде дорівнює kL ...
