Задача 2.
Имеется N камней веса А1,А2,...,АN.
Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза. Если этого сделать нельзя, то указать это.
|
Решение задачи 2.
Основная стратегия решения заключается в том, что каждый следующий камень кладется в кучу с меньшим текущим весом. При этом в первую кучу надо положить камень максимального веса. Покажем, что этого достаточно, чтобы гарантировать правильное решение задачи. По окончании распределения камней по кучам возможны 2 ситуации:
1. Все камни попали во вторую кучу, а ее вес остался меньше половины веса первой кучи. Понятно, что в этом случае камни требуемым образом разбить нельзя, следовательно решения не существует.
2. Случай 1. не верен. Тогда возможны следующие ситуации.
а) Все камни попали во вторую кучу. В этом случае ясно, что веса куч отличаются не более чем на половину первой кучи, если вес первой кучи больше, или не более чем вес последнего камня, положенного во вторую кучу. В любом из этих случаев требуемое условие выполняется.
б) В первую кучу попали и другие камни. Тогда ясно, что веса куч отличаются не более чем на вес самого тяжелого камня, кроме первого. Следовательно и в этом случае условие задачи выполняется.
|
