для третьей задачи, если исключить "Случай 1", то будет несправедлив случай "три одинаковых камня" и близкие к нему. но уже на 5 камнях, всё хорошо. ( на 4 камнях тоже всё хорошо, но это очевидно ).
1 2023-10-11 22:55:34
Re: Вариант задачи разбиения множества чисел. Не понимаю решения (2 ответов, оставленных в Problems)
2 2023-10-11 22:50:05
Re: Вариант задачи разбиения множества чисел. Не понимаю решения (2 ответов, оставленных в Problems)
Доброго времени суток!
А что именно непонятно?
Давайте сначала рассмотрим более "сильный подход":
сначала берём самый тяжёлый камень, потом самый тяжёлый из оставшихся, и так далее;
всегда кладём камень в ту кучу, которая легче (либо в первую,если веса одинаковы)
Все камни попали во вторую кучу, а ее вес остался меньше половины веса первой кучи. Понятно, что в этом случае камни требуемым образом разбить нельзя, следовательно решения не существует.
У Вас три камня: 1 кг, 2 кг, 10 кг. Вы кладёте 10 кг в первую кучу, но во второй будет максимум 3 кг, маловато.
Все камни попали во вторую кучу. В этом случае ясно, что веса куч отличаются не более чем на половину первой кучи, если вес первой кучи больше, или не более чем вес последнего камня, положенного во вторую кучу.
Поскольку мы сразу обозначили, что это не случай 1, то:
либо мы добрали половину веса первой кучи (== самого тяжёлого камня)
либо на предпоследнем камне веса куч сравнялись, но последний камень не может весить больше, чем первый, по условию выбора камней. Вырожденный случай: 3 камня, которые весят одинаково - но даже это удовлетворяет условию "разница не более, чем в 2 раза"
Если подумать, то становится ясно, что этот подход можно смягчить: главное первым взять самый тяжёлый камень, а порядок остальных не так важен. Для камней равного веса всё однозначно, а для неравных весов разница всегда будет меньше, чем вдвое.