Задача про розбиття: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 123:
== Варіанти та узагальнення ==
Існує проблема, звана проблемою з трьома розбивками, яка складається в розбитті множини ''S'' до |''S''|/3 трійок з однаковою сумою. Ця проблема суттєво відрізняється від проблеми розділу і не має псевдо-полиномиального алгоритму часу, якщо '''[[Рівність класів P і NP|P = NP]]'''.<ref name="Garey & Johnson">{{cite book| pages=96–105|title=Computers and Intractability; A Guide to the Theory of NP-Completeness|last1=Garey|first1=Michael|last2=Johnson|first2=David|year=1979|isbn=0-7167-1045-5}}</ref>
Проблема багатосторінкового розділу узагальнює оптимизационную версію проблеми розділу. Тут мета полягає в тому, щоб розбити безліч або мультімножество з {{mvar|n}} цілих чисел на задане число {{mvar|k}} підмножин, мінімізуючи різницю між найменшою і найбільшою сумою підмножини.{{r|multi}}
| |||