Разбивальщик,

6, 10, 6, (1, 2, 8), (4, 3, 4)

11-6 = 5


Как-то ты неоптимально разбил

бухалтер фантоцциПрограмёр,

условие не внимательно почитали, по условию k=4

Да, сообразил уже после того, как ответил (неоднозначно маленько написано :) ). Ну да ладно.

По алгоритму. При прочтении задачи первое о чём мне подумалось: если минимизировать разницу между каждой парой отрезков, то это минимизирует разницу между самым большим и самым маленьким из них.

Кажется работает всегда.

То есть, я бы поступил следующим образом:
1. Разбил ряд на k случайных отрезков
2. Перераспределил бы элементы между первым и вторым из них, минимизируя разницу. Потом между вторым и третьим, третьим и четвёртым и т.д.
3. Если на очередном круге распределения был перераспределён хоть один элемент последовательности, повторил бы шаг 2

Разбивальщик
для примера так и выйдет


средняя сумма 11

а вот как дальше выравнивать, не очень понятно. Здесь справа всё очень ровненько вышло, но в итоге числа 1 и 2 должны уехать во вторую группу...

не представляю простого решения, которое могло бы дать оптимальный результат. Тут только перебором. Моё решение даёт результат близкий к оптимальному :(

можно, конечно, попробовать вариант с минимизацией разницы не в двух соседних отрезках, а в трёх. Но тут я тоже не уверен в 100% оптимальности.

SashaMercuryПрограмёрпропущено...


Да, сообразил уже после того, как ответил (неоднозначно маленько написано :) ). Ну да ладно.

По алгоритму. При прочтении задачи первое о чём мне подумалось: если минимизировать разницу между каждой парой отрезков, то это минимизирует разницу между самым большим и самым маленьким из них.

Кажется работает всегда.

То есть, я бы поступил следующим образом:
1. Разбил ряд на k случайных отрезков
2. Перераспределил бы элементы между первым и вторым из них, минимизируя разницу. Потом между вторым и третьим, третьим и четвёртым и т.д.
3. Если на очередном круге распределения был перераспределён хоть один элемент последовательности, повторил бы шаг 2

К сожалению на практике такие "алгоритмы"(никаким образом не обоснованные) могут привести к ub. Более того, алгоритмом, то что вы написали, ни в коем случае не является вовсе

Он был обоснован базовой логикой решения такой задачи человеком в реальном мире (метод полного перебора исключался, так как является не оптимальным и очевидным изначально).

P.S. Поясни, пожалуйста, какое значение вкладывалось в буквы "ub". Одна только википедия предложила более 2 десятков аббревиатур (не применимых в данном контексте) UB в wiki

SashaMercuryОн ничем не обоснован и совершенно очевидно некорректен, как и ваша последующая идея с тремя элементами.

Любое своё утверждение, не подкреплённое доказательством или статистикой (практикой), я сам же и ставлю под сомнение. Помогает не попадать в глупые ситуации, когда спорил пуская пену изо рта и оказался неправ.

Твоё же утверждение звучит абсолютно (по типу "это так, и никак иначе"). Оно подкреплено доказательством или практическим примером, на котором вариант с тремя элементами даст неоптимальный результат?

SashaMercuryПрограмёрпропущено...


Любое своё утверждение, не подкреплённое доказательством или статистикой (практикой), я сам же и ставлю под сомнение. Помогает не попадать в глупые ситуации, когда спорил пуская пену изо рта и оказался неправ.

Твоё же утверждение звучит абсолютно (по типу "это так, и никак иначе"). Оно подкреплено доказательством или практическим примером, на котором вариант с тремя элементами даст неоптимальный результат?

0. Из частного не следует общее.
1. Слишком очевидно, что это неправильно, потому в данном случае я не привожу конкретные контрпримеры.
2. Задача автора топика классическая. Ее решение указано выше, его асимптотика выше нежели того, что предлагаете вы. Вероятно, над данной задачей думал не один приличный алгорист, и если её классическое решение до сих пор имеет асимптотику выше вашей, ещё раз очевидно, что ваше решение некорректно

А, ну теперь то всё понятно. Не думал, что ты сможешь найти аж 3 таких весомых аргумента. :)
Ладно...

Разбивальщик, когда решишь задачу, кинешь сюда файлик с несколькими десятками входых и выходных массивов? Просто интересно в каком проценте случаев моё решение верно ))