Age: 40 Joined: 01 Feb 2008 Posts: 387 Location: Воронеж
Posted: Thu Aug 20, 2009 12:26 pm Post subject: Задача по нахождению документов оплаты и сумм для фактур
Вопроса как такогого нет. Есть задача, не выдуманая, а реальная, вчера поставили. Я ее разбиваю на несколько подзадач и буду их выкладывать по одной. Если будут какие коментарии по поводу более оптимального алгоритма или кода, я буду только рад. Ну а уж если найдете ошибку, то вообще замечательно, в смысле лучше поправить сразу.
ЗЫ: сначала попробуйте сами, потом уж в нете я там сам искать умею.
Подзадача 1. Есть набор чисел A = {a_1, a_2, ..., a_n} (сумма позиций документа выравнивания) и есть число S_1 (сумма фактуры). Нужно подобрать поднабор позиций что бы их сумма была равна сумме фактуры, т.е. S_1 = a_i + a_j + ... + a_p.
После обеда займусь реализацией алгоритм уже кое какой готов. _________________ Hормальные люди делают вещи намного более безумные чем всё, что делают сумасшедшие (c) С.Лем
Last edited by XXX_:) on Thu Aug 20, 2009 5:33 pm; edited 1 time in total
таких поднаборов может быть несколько, каким образом будет находится тот единственный, к-й нужен? Как я понимаю, необходимо выделить только одно множество позиций, сумма по которым будет равняться сумме фактуры.
Age: 40 Joined: 01 Feb 2008 Posts: 387 Location: Воронеж
Posted: Thu Aug 20, 2009 5:32 pm Post subject:
Забегу немного вперед. много фактур(обозначим подмножество S = S_1, ..., S_m), они все ссылаются на один документ выравнивания(подмножество A). Берем одну фактуру(Т.е S_1(переправил верхний пост)) для нее ищем подмножество(а_s,...,a_j). После этого будем осуществлять поиск для следующей фактуры (S_2), но позиции, участвовавшие в первой сумме (а_s,...,a_j), во вторую входить не могут.
Интуиция говорит, что будет больше шансов такое сделать, если в первую подсумму выбирать как можно большие a_i, т.е. вести поиск сначала по большим по значению элементам a_i, где i от 1 до n.(Хотя я думаю есть варианты когда это будет не оптимально). _________________ Hормальные люди делают вещи намного более безумные чем всё, что делают сумасшедшие (c) С.Лем
Last edited by XXX_:) on Thu Aug 20, 2009 5:54 pm; edited 1 time in total
Age: 48 Joined: 25 Jan 2008 Posts: 580 Location: Москва
Posted: Thu Aug 20, 2009 5:37 pm Post subject:
А чем не устраивает вариант FIFO, с частичным выравниванием позиции платежа, сумма по которой будет превышать остаток от разности суммы фактуры и предыдущих позиций? _________________ С уважением,
Удав.
Age: 48 Joined: 25 Jan 2008 Posts: 580 Location: Москва
Posted: Thu Aug 20, 2009 5:40 pm Post subject:
Ага. Новая вводная
А кто мешает не в одном документе выравнивания все делать, а отдельным документом для каждой фактуры? _________________ С уважением,
Удав.
Age: 40 Joined: 01 Feb 2008 Posts: 387 Location: Воронеж
Posted: Thu Aug 20, 2009 5:52 pm Post subject:
Удав wrote:
Ага. Новая вводная
А кто мешает не в одном документе выравнивания все делать, а отдельным документом для каждой фактуры?
В системе у нас вот так реализовано. А то что я делаю, нужно для отчета "Кредитная история" т.е. пляшем от фактур, ради одного отчета концепт пересматривать не будут.
Наши FI сказали, что то что мы хотим можно реализовать только подбором позиций на нужную сумму, с последующим переходом к документам оплаты. Но это будет потом. Сначала корректно разобраться с 1 подзадачей. Могу выложить полный алгоритм. Просто боюсь мозг забью людям.
Если кому интересно, то это, наверное, частный случай задачи об упаковки рюкзака. Не бейте если не так _________________ Hормальные люди делают вещи намного более безумные чем всё, что делают сумасшедшие (c) С.Лем
Age: 40 Joined: 01 Feb 2008 Posts: 387 Location: Воронеж
Posted: Mon Aug 24, 2009 4:49 pm Post subject:
Мои изыскания привели к следующим результатам. Опросил всех кто был в досигаемости.
Абаперы: интересно, сочувствуем, если сделаешь расскажи
Научный руководитель(математик): посмеялся, сказал алгоритм на оптимальное решение такой задачи тянет на кандидатскую. Сказал, если сделаю, чтобы обязательно рассказал.
Интернет: Есть задача, когда множество S состоит из одного числа, тогда алгоритм есть. Такая задача называтся "Задача о суммах подмножеств". Но алгоритм ее решения находится на последних страницах книги "Алгоритмы: построение и анализ" почти в 1300 страниц. Полистал ее в магазине, понял что сходу не понятно. Приобрести помешала природная жадность. Времени на ее освоение вне работы просто нет.
В электронном формате книга обрезана до 16 главы. Если у кого есть скиньте, может что интересного вычитаю.
ЗЫ: по возможности отложу на неопределенный срок... _________________ Hормальные люди делают вещи намного более безумные чем всё, что делают сумасшедшие (c) С.Лем
Age: 40 Joined: 01 Feb 2008 Posts: 387 Location: Воронеж
Posted: Fri Sep 04, 2009 12:26 pm Post subject:
Имел неосторожность или еще как, в общем когда интересовался решением этой задачи у своих коллег мой начальник так же стоял в копии. Увидел это безобразие и написал постановщику гневное письмо . Задачу сняли/отложили. Алгоритм по нахождению одного подмножества есть схематично, по ссылке http: /forum.vingrad.ru/index.php?showtopic=53676 (отдельное спасибо vga, кстати решил купить себе такую в печатном варианте) в "Задача о суммах подмножеств" последние страницы криги. Хотя алгоритм для нахождения одного подмножества не составляет труда.
Я как мне кажется придумал алгоритм для нахождения для любого конечного набора S_i, только вот реализовать его незнаю как , т.е. можно, но сложно, если интересно могу выложить.
А самому реализовывать некогда работы очень много как всегда, да еще дисер пишу, защита скоро время поджимает.
Буду рад, если кого то эта задача заинтересовала , если у кого есть желание поработать в комманде над этой задачей я только за. _________________ Hормальные люди делают вещи намного более безумные чем всё, что делают сумасшедшие (c) С.Лем
Age: 40 Joined: 01 Feb 2008 Posts: 387 Location: Воронеж
Posted: Fri Sep 04, 2009 12:41 pm Post subject:
прошу технические детали оставить на потом.
алгоритм примерно такой
1. берем S_1 и для него находим все возможные суммы из {x_i}.
Запомним индексы i из каждой суммы. Примерно так
S_1 индексы 2, 5, 34, 1
S_1 индексы 2, 16, 26
....
S_1 индексы 16, 17, 37
Так сделать для всех S_j
2. Дальше нужно выбрать такие строки из таблицы с индексами, чтобы
слева было S_1, S_2, ...
а справа цифры не повторялись. Такое решение по крайней мере одно есть точно.
Может есть у кого другая стратегия? _________________ Hормальные люди делают вещи намного более безумные чем всё, что делают сумасшедшие (c) С.Лем
На самом деле приведенная задача - это классическая задача "заполнения стакана". Частный случай диофантового уравнения. Решается либо полным перебором, а если позиций тысячи (их полностью не перебрать), то методом ветвей и границ - немного улучшенный полный перебор.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum You cannot attach files in this forum You can download files in this forum
All product names are trademarks of their respective companies. SAPNET.RU websites are in no way affiliated with SAP AG. SAP, SAP R/3, R/3 software, mySAP, ABAP, BAPI, xApps, SAP NetWeaver and any other are registered trademarks of SAP AG. Every effort is made to ensure content integrity. Use information on this site at your own risk.
я там сам искать умею.
. 