Задача про розбиття: відмінності між версіями

Цей алгоритм може бути поширений на випадок {{math|''k'' > 2}} множин: для того, щоб узяти {{mvar|k}} найбільших елементів і для кожного розбиття їх розширює розділ, послідовно додаючи інші елементи в залежності від того, який набір менше. (Проста версія вище відповідає {{math|''k'' {{=}} 2}}.) Ця версія працює в часі {{math|''O''(2^''k'' ''n''²)}} і, як відомо, дає {{math|{{sfrac|(''k'' + 2)|(''k'' + 1)}}}} [[Апроксимація|наближення]].<ref name="Graham" /> Таким чином, ми маємо схему наближення поліноміального часу (PTAS)для завдання про розбиття чисел, хоча це не повністю поліноміальна схема наближення часу (час роботи є експоненціальним у гарантованій задачі наближення). Однак існують варіанти цієї ідеї, які є повністю поліноміальними схемами апроксимації для завдання підмножини, а отже, і для завдання розбиття.<ref name=knapsack/><ref name="MartelloToth">{{cite book |chapter=4 Subset-sum problem|pages=105–136| title = Knapsack problems: Algorithms and computer interpretations | last1=Martello|first1=Silvano|last2=Toth|first2=Paolo| publisher =Wiley-Interscience | year = 1990 | isbn = 0-471-92420-2|mr=1086874|ref=harv}}</ref>