1 Отредактировано gesperid (2022-08-17 08:49:06)

Тема: Вариант задачи разбиения множества чисел. Не понимаю решения

Добрый день! Может быть кто-нибудь поможет, наведет на мысли?
Эти задачи с объяснения видел на нескольких сайтах (например, http://algolist.ru/olimp/sor_prb.php) На форумах приведена куча реализаций этих решений.
Но я не понимаю объяснение. Можно ли эти решения как-то более строго и вместе с тем наглядно доказать/показать?

Задачи:

Задача 2.
Имеется N камней веса А1,А2,...,АN.
Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза. Если этого сделать нельзя, то указать это.

Задача 3.
Условие задачи 2, только веса куч отличаются не более, чем в 1,5 раза.

"Решения":
Решение задачи 2.

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

1. Все камни попали во вторую кучу, а ее вес остался меньше половины веса первой кучи. Понятно, что в этом случае камни требуемым образом разбить нельзя, следовательно решения не существует.

2. Случай 1. не верен. Тогда возможны следующие ситуации.

а) Все камни попали во вторую кучу. В этом случае ясно, что веса куч отличаются не более чем на половину первой кучи, если вес первой кучи больше, или не более чем вес последнего камня, положенного во вторую кучу. В любом из этих случаев требуемое условие выполняется.

б) В первую кучу попали и другие камни. Тогда ясно, что веса куч отличаются не более чем на вес самого тяжелого камня, кроме первого. Следовательно и в этом случае условие задачи выполняется.

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

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

2

Re: Вариант задачи разбиения множества чисел. Не понимаю решения

Доброго времени суток!
А что именно непонятно?
Давайте сначала рассмотрим более "сильный подход":

  • сначала берём самый тяжёлый камень, потом самый тяжёлый из оставшихся, и так далее;

  • всегда кладём камень в ту кучу, которая легче (либо в первую,если веса одинаковы)

Все камни попали во вторую кучу, а ее вес остался меньше половины веса первой кучи. Понятно, что в этом случае камни требуемым образом разбить нельзя, следовательно решения не существует.

У Вас три камня: 1 кг, 2 кг, 10 кг. Вы кладёте 10 кг в первую кучу, но во второй будет максимум 3 кг, маловато.

Все камни попали во вторую кучу. В этом случае ясно, что веса куч отличаются не более чем на половину первой кучи, если вес первой кучи больше, или не более чем вес последнего камня, положенного во вторую кучу.

Поскольку мы сразу обозначили, что это не случай 1, то:

  • либо мы добрали половину веса первой кучи (== самого тяжёлого камня)

  • либо на предпоследнем камне веса куч сравнялись, но последний камень не может весить больше, чем первый, по условию выбора камней. Вырожденный случай: 3 камня, которые весят одинаково - но даже это удовлетворяет условию "разница не более, чем в 2 раза"

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

3

Re: Вариант задачи разбиения множества чисел. Не понимаю решения

для третьей задачи, если исключить "Случай 1", то будет несправедлив случай "три одинаковых камня" и близкие к нему. но уже на 5 камнях, всё хорошо. ( на 4 камнях тоже всё хорошо, но это очевидно ).