Задача о количестве вещества

[RReverser]

В результате проведения эксперимента за один раз образуется заранее неизвестное количество некоторого вещества. Эксперимент проводят N (3<=N<=10000) раз. Полученное вещество в порядке проведения экспериментов распределяют по контейнерам, общим количеством K (2<=K<=400, K<=N).
Необходимо таким образом распределить вещество по контейнерам, чтобы общее количество вещества в наиболее заполненном контейнере было наименьшим.

Формат входных данных.
Первая строка входного файла SUBSTAN.DAT содержит два натуральных чисел N (3<=N<=10000) но K (2<=K<=400, K<=N). Во второй строке находятся N целых положительных чисел, каждое из которых означает количество полученного вещества в соответствующем эксперименте. Все числа между собой разделены пробилами.


Формат выходных данных.
Единственная строка исходного файла SUBSTAN.SOL должен содержать одно целое число общее количество вещества в наиболее заполненном контейнере.

Пример.

SUBSTAN.DAT
7 2
2 5 1 11 2 3 2

SUBSTAN.SOL
18

Так как возможны варианты размещения в контейнерах:

1. 2=2 5+1+11+2+3+2=24
2. 2+5=7 1+11+2+3+2=19
3. 2+5+1=8 11+2+3+2=18
4. 2+5+1+11=19 2+3+2=7
5. 2+5+1+11+2=21 3+2=5
6. 2+5+1+11+2+3=24 2=2

При этом самый заполненный контейнер будет иметь наименьшее кол-во вещества при разделении №3.

Жадным алгоритмом проходит не все тесты, а полным перебором надо 2^400(кажется) вариантов. Буду благодарен за возможный вариант решения задачи (желательно на Паскале).

[Naeel Maqsudov]

Интересно.... Олимпиадная задача...
Однако, если я все правильно понял, то для условия
7 2
2 5 1 11 2 3 2

есть вариант
11=11 1+2+2+2+3+5=15

И наиболее заполненный контейнер содержит 15
Следовательно ответ не 18, а 15
Я прав? Или я чего-то недопонял в условии?

[airyashov]

у меня почему-то получается
так
11+1+2=14
5+2+3+2=12

[airyashov]

как понимаю местами менять нельзя полученное вещество?

[Naeel Maqsudov]

Да. оптимальное решение 14! Как я его упустил
Про "нельзя менять местами" в условии ничего не сказано.

[RReverser]

Просто оптимальное распределение по порядку действительно 14 и 12(14), но, как сказано в условии, образуется заранее неизвестное количество и вещество в порядке проведения экспериментов распределяют по контейнерам, то есть задача сводится до оптимального разделения данного ряда чисел на k частей. Именно такую задачу и необходимо решить.

[RReverser]

как понимаю местами менять нельзя полученное вещество?

Как уже говорилось, вещество разделяется в порядке проведения єкспериментов, что и подразумевает под собой невозможность обмена веществ местами.

[RReverser]

Пожалуйста, дайте какой-нить вариант, потому что мне до пятницы решение отдать надо. Получилось оптимизировать перебор где-то на 50%,но при К=400 это мало помогает, полчаса ждал, потом вырубил, надоело. Еще получалось "интелектуальным" вариантом(что-то типа нейросетей,угадывание),в лимит времени вкладывается, но зато появилась возможность ошибки, иногда до 8%,а надо результат с точностью до единицы. Может, хоть кто-то умный здесь есть и поможет решить такую простую задачку?

[Naeel Maqsudov]

1) А честно ли будет, считав значения из исходного файла, первым делом подсчитать сумму количества вещества и поделить на число контейнеров?

2) Я бы (исходя из фабулы задачи) в каждом следующем опыте добавлял бы полученное вещество бы в наиболее пустой контейнер. Т.е. ищем минимум, прибавляем к нему Вещество. Но этот алгоритм дает результат 14, а не 18.

К1:2 (2)
К2: (0)

К1:2 (2)
К2:5 (5)

К1:2,1 (3)
К2:5 (5)

К1:2,1,11 (14)
К2:5 (5)

К1:2,1,11 (14)
К2:5,2 (7)

К1:2,1,11 (14)
К2:5,2,3 (10)

К1:2,1,11 [highlight](14)[/highlight]
К2:5,2,3,2 (12)

Приведите другие тестовые данные. Мне кажется нам придется подгорять алгоритм под ответы

[Naeel Maqsudov]

Так как возможны варианты размещения в контейнерах:
......

Если данный вариант размещения правильный (хотя на мой взгляд он фабуле задачи совершенно не соответствует), то кроме полного поеребора я не вижу иных алгоритмов. Можно попробовать оптимизировать полный перебор отказавшись отпобсчета сумм вещества на каждой итерации, а подсчитывать его аддитивно. Т.е. рассчитав все суммы до первой итерации, а на каждом шаге просто "перекладывать" вещество в соседний койтейнер.