Как разделить множество на K подмножеств так, чтобы сумма элементов в подмножествах была минимальной?

Question

Как разделить множество на K подмножеств так, чтобы сумма элементов в подмножествах была минимальной?

Я изучаю DP, и эта проблема возникла у меня, когда я читал алгоритм Balanced Partition. В этом алгоритме мы можем разделить список на два списка, так что сумма элементов этих списков равна. Но что, если мне нужны K списков и мне нужно, чтобы они имели минимальную сумму? Я думал об изменении алгоритма Balanced Partition для решения этой проблемы, но на самом деле не мог найти способ сделать это.

Пусть S будет {1,1,5}, оптимальное решение для K = 2 будет {1,1}, {5}.

Есть намеки?
Заранее спасибо.

1

algorithm c++dynamic-programming greedy

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Простой алгоритм будет:

sort S in descending order
for each element in S:
put it into the partition with the smallest sum

Это бы поставить 5 в первый раздел и 1s во втором разделе в вашем примере (K = 2).

0