Це доведено, що Алгоритм диференціації Кармаркар-Карпа завжди виконує краще ніж жадібний за Двосторонні розділи проблеми, тобто розбиття набору з n цілих чисел на 2 підмножини з однаковими сумами. Чи може це поширюватися на К-поділ розділу так само? Якщо ні, чи є який-небудь приклад, де жадібний виступає краще, ніж KK, у розділі k-way?
Відповіді:
0 для відповіді № 1КК "с перевага не можу бути узагальненою для розділення k-шляху. Фактично, легше дати зустрічний приклад, де Жадний алгоритм працює краще. Нехай показник продуктивності є максимальною сумою кінцевого розділу. Тепер візьміть цей набір цілих чисел:
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, жадібний виконано краще для цього прикладу.