Задача про розбиття: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 88:
</source>
Цей алгоритм може бути поширений на випадок {{math|''k'' > 2}} множин: для того, щоб узяти {{mvar|k}} найбільших елементів і для кожного розбиття їх розширює розділ, послідовно додаючи інші елементи в залежності від того, який набір менше. (Проста версія вище відповідає {{math|''k'' {{=}} 2}}.) Ця версія працює в часі {{math|''O''(2<sup>''k''</sup> ''n''<sup>2</sup>)}} і, як відомо, дає {{math|{{sfrac|(''k'' + 2)|(''k'' + 1)}}}} [[Апроксимація|наближення]].<ref name="Graham" /> Таким чином, ми маємо схему наближення поліноміального часу (PTAS)для завдання про розбиття чисел, хоча це не повністю поліноміальна схема наближення часу (час роботи є експоненціальним у гарантованій задачі наближення). Однак існують варіанти цієї ідеї, які є повністю поліноміальними схемами апроксимації для завдання підмножини, а отже, і для завдання розбиття.
=== Дифференціальний алгоритм ===
|