Добрый день! Может быть кто-нибудь поможет, наведет на мысли?
Эти задачи с объяснения видел на нескольких сайтах (например, http://algolist.ru/olimp/sor_prb.php) На форумах приведена куча реализаций этих решений.
Но я не понимаю объяснение. Можно ли эти решения как-то более строго и вместе с тем наглядно доказать/показать?
Задачи:
Задача 2.
Имеется N камней веса А1,А2,...,АN.
Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза. Если этого сделать нельзя, то указать это.
Задача 3.
Условие задачи 2, только веса куч отличаются не более, чем в 1,5 раза.
"Решения":
Решение задачи 2.
Основная стратегия решения заключается в том, что каждый следующий камень кладется в кучу с меньшим текущим весом. При этом в первую кучу надо положить камень максимального веса. Покажем, что этого достаточно, чтобы гарантировать правильное решение задачи. По окончании распределения камней по кучам возможны 2 ситуации:
1. Все камни попали во вторую кучу, а ее вес остался меньше половины веса первой кучи. Понятно, что в этом случае камни требуемым образом разбить нельзя, следовательно решения не существует.
2. Случай 1. не верен. Тогда возможны следующие ситуации.
а) Все камни попали во вторую кучу. В этом случае ясно, что веса куч отличаются не более чем на половину первой кучи, если вес первой кучи больше, или не более чем вес последнего камня, положенного во вторую кучу. В любом из этих случаев требуемое условие выполняется.
б) В первую кучу попали и другие камни. Тогда ясно, что веса куч отличаются не более чем на вес самого тяжелого камня, кроме первого. Следовательно и в этом случае условие задачи выполняется.
Решение задачи 3.
На начальном этапе в первую кучу кладется самый тяжелый камень, а во вторую - два следующих по весу камня. Для оставшихся камней реализуется описанная для задачи 2 стратегия.