Доказано е, че Алгоритъмът на Кармаркар-Карп за различаване винаги се представя по-добре от алчен за 2-лентово разделяне проблеми, т.е. разделяне набор от N цели числа на 2 подгрупи с еднакви суми. Може ли това да бъде разширено k-път разделяне както и? Ако не, има ли някакъв пример, където алчните изпълняват по-добре от KK в разделянето на k-way?
Отговори:
0 за отговор № 1КК "S превъзходство не мога да бъдат обобщени за разделянето на k-way. Всъщност е по-лесно да дадете контра-пример, където Грозен алгоритъм е по-добре. Нека измерването на ефективността да бъде максималната сума от подразделенията на последния дял. Сега вземете този набор от числа:
S = [10 7 5 5 6 4 10 11 12 9 10 4 3 4 5] и k = 4 (разделяне на 4 равни подгрупи)
Превъртане напред, KK алгоритъм дава резултат от [28, 26, 26, 26], докато алчният дава последната деление на [27, 27, 27, 24]. От 28> 27, алчен за този пример.