Задача о камнях

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

Пусть – множество, элементы которого являются номерами камней, содержащихся в куче :

Для удобства введем переменную – номер кучи, в которую помещен камень .

Для решения задачи нужно найти минимум функции:

Решение задачи

Предлагается следующий жадный алгоритм. На каждом шаге будем брать самый тяжелый камень из оставшихся и класть его в самую легкую кучу. Пусть камни упорядочены по убыванию весов:

.

Обозначим через – вес кучи . Псевдокод алгоритма имеет следующий вид:

for i = 1 to m do
 b[i] = 0
for j = 1 to n do
  k = argmin(b[i]) # i = 1,...,m
  x[j] = k
  b[k] = b[k] + v[j]

---

Источник