Дележ золота

Разминка для мозгов » Задачи » Дележ золота

Добавлено: 04.02.09 в 12:15

Два золотоискателя намыли на прииске N золотых самородков весом w₁, w₂, ... w_n.

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

Вывести номера самородков, которые достались первому старателю.

У этой задачи пока что нет ответа/решения. Вы можете прислать свой вариант в комментарии.

Комментарии

Google says:

Sarge (22.01.13):

На вероятность задача? Последняя фраза намекает

Аноним (12.05.13):

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

ddipp (17.11.14):

Самородки в массиве w. Отсортировать.
Золотоискатели: z1, z2
Далее в цикле i по массиву w от самых тяжелых к легким:
Если общий вес у z2 меньше чем у z1, то самородок w[i] отдать z2, иначе отдать z1.

Таким образом первый самый тяжелый самородок будет у первого старателя, пока вес следующих не превысит вес самого тяжелого, самородки отдаются второму. Далее более-менее равномено распределяются, причем чем дальше мы идем по массиву w, вес самородков уменьшается и достигается бОльшая точность

ddipp (17.11.14):

ответить

		Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи. Petruchek.Info

Petruchek.Info

Дележ золота