Сумма чисел в массиве, наиболее приближающаяся к необходимой , Заполнение интервала времени кусочками заданной длины

Цитата Swetlana @ 23.11.12, 14:06

скажите, можно ли "излишек" с одного документа разделить на несколько документов с "недостачей"?

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

тогда всё решается быстро и точно алгоритмом построения максимального потока в сети
я всегда пользуюсь для этого методом фаз Диница

Вначале нужно сделать сетевую постановку задачи, то есть построить граф, на котором всё будет происходить.

1. Отмечаем вершину-фиктивный источник s0, из него поток выходит.
2. Пусть у вас K документов с излишками. Берём ещё K вершин s1, ...,sk.
Соединяем фиктивный источник s0 с вершинами si, i=1..K.
Полагаем пропускную способность дуги s0->si C[s0, si] равной излишку i-го документа.
3. Отмечаем вершину фиктивный сток t0, в него поток приходит.
4. Пусть у вас R документов с недостачей. Берём ещё R вершин t1, ...,tr.
Соединяем вершины tj, j=1..R c фиктивным стоком t0.
Полагаем пропускную способность дуги tj->t0 C[tj, t0] равной недостаче j-го документа.
5. Соединяем каждую вершину-источник si со всеми вершинами-стоками tj, i=1..K; j=1..R.
Пропускные способности получившихся дуг полагаем равными +бесконечности.

Сеть построена. Теперь стандартным алгоритмом строим в сети максимальный поток из s0 в t0.
Величина потока в дугах s0->si - сколько надо забрать с i-го документа.
Величина потока в дугах tj->t0 - сколько надо добавить к j-му документу.

Сообщение отредактировано: Swetlana - 23.11.12, 14:43

Цитата Swetlana @ 23.11.12, 14:42

тогда всё решается быстро и точно алгоритмом построения максимального потока в сети

Наконец-то дошли руки попробовать решить мою задачу алгоритмом построения максимального потока в сети.
Воспользовался методом фаз Диница. И все вроде бы хорошо, но не совсем.

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

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

У вас вообще 3 варианта исходных задач.
1. Суммарный избыток = суммарная недостача. Алгоритм полностью восполняет недостачу, убирает избыток.
2. Суммарный избыток > суммарная недостача. Недостача устранена, остаток избытка остался.
3. Суммарный избыток < суммарная недостача. Избыток устранен, остаток недостачи остался.

Вы же понимаете, что решение не единственно, алгоритм построения максимального потока предлагает одно из возможных решений.
Если вы минимизируете количество операций с документами, то делайте "предобработку" - находите 2 документа типа
недостача = избытку и погашайте их сами. А когда таких документов не останется, запускайте построение максимального потока.

поняла, что неправильно сделала постановку задачи
сори

в этой задаче надо минимизировать количество операций с документами, чего максимальный поток не делает
подумаю на досуге...

вот ещё одна задачка на набор сумм или одномерную упаковку
надо сделать постановку задачи

Имеется n предметов положительной вещественной стоимости (рубли-копеки, вообще говоря).
Имеется m контейнеров, m-1 контейнер положительной вместимости, m - безразмерный, m>=3.
Размерность большая. Предметов примерно 200, суммы большие.
Что нового - контейнеры с приоритетами. Пусть они упорядочены по убыванию приоритетов.

1. Можно назначить контейнерам какие-то веса и минимизировать взвешенную сумму отклонений. Вопрос - как приписать веса.
2. Можно набирать по отдельности, начиная с самой приоритетной суммы, но тут можно здорово промахнуться.
Какие ещё идеи?

если ДП будет тормозить
1. вначале наиболее крупные слагаемые раскидать по набираемым суммам, чтобы значительно их уменьшить
2. добирать остатки ДП

Здравствуйте! Почитал разных тем. Понял что задача распространённая. У меня есть аналогичная задача, но числа не целые. Нашёл кучу скриптов и макросов под Excel, работают хорошо, но мне под с++ надо ((. Помогите пожалуйста чем нибудь, лучше примером. Алгоритмы с целыми числами смотрел, но я так понимаю они мне не подходят.

Вот один из примеров:

2 446,721
1 251,340 1794,935
464,372
543,595

Решение всегда есть 100% и оно единственное, точность 0, слагаемых любое количество.

>У меня есть аналогичная задача
Какая именно?

>но числа не целые
числа из примера можно умножить на 1000

Цитата MBo @ 21.05.13, 02:39

>Какая именно?

Есть числа:

2 446,721
1 251,340
464,372
543,595

Нужно узнать какие из них составляют заданное число 1794,935. Решение всегда есть 100% и оно единственное, точность 0, слагаемых любое количество.

>числа из примера можно умножить на 1000
Спасибо, это вроде упрощает жизнь. Тогда можно использовать алгоритм Swetlana для подбора гирь?

>Тогда можно использовать алгоритм Swetlana для подбора гирь?
В общем, да.

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

>слагаемых любое количество.
Кстати, какое реальное количество?
Если в пределах двух десятков, то будет быстрее перебрать все 2^N вариантов, поскольку динамическое программирование медленно будет работать для большой суммы

>Кстати, какое реальное количество?

Возможно и больше 20, а что тогда посоветуете? Есть ли такие решения?

сложность перебора 2^N
динамического программирования N * Sum
Вот, исходя из параметров, и надо выбирать метод.

Если разброс значений существенный, то еще можно с помощью ДП по округленным значениям и уменьшенной сумме найти вероятные решения, затем проверить их.

В общем применил алгоритм описанный в посте 29, для 25 слагаемых и 7-значной суммы работает шустро. Спасибо за код!