Алгоритм оптимального сопоставления

Подскажите алгоритм оптимального сопоставления проводок по кол-ву (с минимазацией количества разбиений)

[MironovI]

А что это такое позвольте неврубиться сходу? )

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

[Maximin]

В качестве наиболее вероятного варианта представляется reverse order by AmountCur по кредиту и дебету, соответственно.

к сожалению, не все так просто, вот контрпример:
------------------------
3 -7
3 -3
2
2
-----------------------

[Maximin]

Впрочем, особого смысла это не имеет. К тому же, предложенный мной способ не обязательно даст минимальное кол-во разбиений. Чистая эвристика.
Вообще - задача динамического программирования, кстати. На одной из олимпиад в моем прошлом, кстати, подобная задача была.

[AndyD]

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

[itfs]

У меня такая мысль. Я думаю, Вы сразу продвинетесь, если немного поработаете над моделью распределения для сопоставленй. Статистика ведь имеется?

Например:
1:1 - 55%
1:n = n:1 - 20% (симметрично)
n:n - 5%

(Это только для примера, на самом деле, у Вас может получиться и что-нть получше.)

Далее, очевидно, перебираем ветки от наиболее вероятной к менее.
Тогда задача оптимальности последнего случая, который Вы считаете общим и потому рассматриваете, станет не такой критичной.

С уважением, itfs.

[AndyD]

А если, допустим, 1:1 не будет? И как все-таки выбрать в остальных случаях? Ведь первоначально вопрос так и ставился.

[itfs]

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

С уважением, itfs.

[Recoilme]

Цитата:

Изначально опубликовано ahtoh
Подскажите алгоритм оптимального сопоставления проводок по кол-ву (с минимазацией количества разбиений)

А зачем, если не секрет????

Цитата:

А зачем, если не секрет????

хочу сделать аксапту лучше

[zinius]

Не удалось сделать аксапту лучше?
Пытаюсь найти аналогичный алгоритм для сопоставления кучи проводок по подотчетникам

[belugin]

Цитата:

Сообщение от AndyD

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

Задача об упаковке в контейнеры