Есть N сумм и M "контейнеров" (не могу точное слово подобрать), по которым нужно распределить эти суммы.
Причем n1 + n2 + ... nN = m1 + m2 + ... mM.
Суммы и контейнеры могут быть отрицательные.
Пример: 5 распределяем по двум контейнерам 2 и 3, тут все просто, в первый пишем 2, во второй 3. Нельзя писать в первый 3, а во второй 2, "емкость" должна быть заполнена точно.
Пример еще: 10 красных и 1 синий (N=2) распределяем по двум контейнерам 5 и 6. В 5 пишем 5 красных, в 6 пишем 5 красных и 1 синий.
Пример еще: 10 красных и -1 синий (N=2) распределяем по двум контейнерам 15 и -6. В 15 пишем 10 красных и 5 синих, в -6 пишем -6 синих.
Смысл я думаю понятен.
Думаю есть простое и изящное решение.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, flonder, Вы писали:
F>>Смысл я думаю понятен.
W>
Ну представьте разноцветные шары, которые нужно распределить по стаканам разной высоты, наполнив их полностью. Тут трудность в том, что разных шаров может быть отрицательное количество и положительное, и стаканы могут быть отрицательной высоты.
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, flonder, Вы писали:
F>>Думаю есть простое и изящное решение. S>Для общего случая нет. Wiki. SO
Это не совсем то. Тут не нужно искать минимумы и максимумы. Сумма предметов уже точно совпадает с емкостью рюкзаков. Тут проблема в другом, что они могут быть отрицательные.
Здравствуйте, flonder, Вы писали:
F>Ну представьте разноцветные шары, которые нужно распределить по стаканам разной высоты, наполнив их полностью. Тут трудность в том, что разных шаров может быть отрицательное количество и положительное, и стаканы могут быть отрицательной высоты.
И всё, никаких больше ограничений?
Тогда тем более не ясно с чем проблема. Бери любой стакан с отличной от нуля ёмкостью и заполняй его шарами пока его ёмкость не станет нулевой. Повтори для всех остальных стаканов.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, flonder, Вы писали:
F>>Ну представьте разноцветные шары, которые нужно распределить по стаканам разной высоты, наполнив их полностью. Тут трудность в том, что разных шаров может быть отрицательное количество и положительное, и стаканы могут быть отрицательной высоты.
W>И всё, никаких больше ограничений? W>Тогда тем более не ясно с чем проблема. Бери любой стакан с отличной от нуля ёмкостью и заполняй его шарами пока его ёмкость не станет нулевой. Повтори для всех остальных стаканов.
Всего шаров может быть меньше, чем в одной емкости. 2 = +5 -3
Здравствуйте, flonder, Вы писали:
W>>Тогда тем более не ясно с чем проблема. Бери любой стакан с отличной от нуля ёмкостью и заполняй его шарами пока его ёмкость не станет нулевой. Повтори для всех остальных стаканов.
F>Всего шаров может быть меньше, чем в одной емкости. 2 = +5 -3
Ну и что? Продолжай заполнять.
Остались стаканы с ненулевой ёмкостью? Бери красные шары и продолжай их заполнять. На каждый добавленный таким образом красный шар просто добавляй антикрасный в общую кучу.
Или даже вот тебе ещё более простой алгоритм: берёшь все свои исходные шары и ссыпаешь их в первый стакан, потом заполняешь синими шарами все стаканы чтобы их ёмкость стала нулевой — вот и готово другое разбиение.
Ну и даже если считать что цветов лишь пара, то различных разбиений будет счётное число — выбирай любое.
Здравствуйте, flonder, Вы писали:
F>Ну представьте разноцветные шары, которые нужно распределить по стаканам разной высоты, наполнив их полностью. Тут трудность в том, что разных шаров может быть отрицательное количество и положительное, и стаканы могут быть отрицательной высоты.
Здравствуйте, flonder, Вы писали:
F>Это не совсем то. Тут не нужно искать минимумы и максимумы. Сумма предметов уже точно совпадает с емкостью рюкзаков. Тут проблема в другом, что они могут быть отрицательные.
