Есть таблица:
Орг1 | Орг2 |Долг
A    | B    |300
B    | C    |400
C    | A    | 500

В таблице показан долг организации 1 перед организацией 2, требуется найти наиболее оптимальный путь погашения долга организациями( по другому не знаю как сформулировать)

Из этой таблицы наиболее оптимальным получается :
Организация В должна Организации А 100
И Организация С должна Организации А 100. КАК решить такую задачу запросом?? Помогите кто решал такое

оптимальный путь погашения долга - что значит?

(0) Если запросом, то используй функцию:
ВЫБОР
   КОГДА <Выражение> ТОГДА <Выражение>
       ИНАЧЕ <Выражение>
   КОНЕЦ

Интересно... А организации-то в курсе, что за них программа будет решать, кто, сколько и кому будет платить? :)

(3) Может у них холдинг.

(4) ну и что?

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

(1) оптимальный путь: А должна Б 100 , а Б должна С 100, следовательно А может отдать С 100 и всё (ничего не отдавая Б)

Смотри в сторону динамического программирования

(8) весь смысл решить её обычным запросом (

(0) загнать в проводки на АП счет - и получить итоги;
кредитовый остаток должен заплатить, дебетовый получить (ну или наоборот - всегда путаю что слева что справа))))

(10) мож я не полностью описал начальные данные: вот есть пустая конфа , создаём какой нить регистр долги, в нём измерения Орг1 , орг2, ресурс долг  и всё, больше нет ничего

(10) кстати так  вроди не будет видно кто кому должен заплатить: так же можно сделать проще, выбрать должника с минусом , выбрать получателей с плюсом и объединить всё, только опять же не видно кто кому должен

что то вроде того:
А - 300
В - 400
С - 500

Объеденить всё

В  300
С  400
А  500

Получим А  200
       В -100
       С -100  чисто логически можно догадаться что В должна А 100 и С должна А 100,
но это простейший пример, а если будет гораздо больше данных, то и не разберёшь кто кому должен

Может как-то так:
Развернуть таблицу в:

A: -300
B: +300
B: -400
C: +400
C: -500
A: +500

Объединить, получается:
А: +200
B: -100
C: -100

Дальше у кого "минус", отдают тем у кого "плюс" (Так примерно долги по FIFO гасятся).

Если количество организаций ограничено?

Определить общие суммы платежей организаций очень просто, сложно определить кому именно должны заплатить организации :))

(16) вот и я про это же

(17) А ты уже придумал, как определить общие суммы платежей? :))

(15) коичество не ограничено

(13) и (14) вроди это и есть

(20) В (13) и (14) ни о чем :))

ну значит я тупой )))

(19) Если не ограничено, то ИМХО в запросе (1с-ком) это не решаемо

(24) Да пока и сам алгоритм-то не ясен, пусть даже без запроса :))

(24) а если ограничено???

в запросах нет нарастающего итога

(27) При чем здесь нарастающий итог?

(28) да это я предположил что возможно её как то так решить,т.к. где то видел подобную задачу котрая решается через нарастающие итоги

(0) Задача решается рекурсивно.

(30) Как? :))

(26) Я бы начал в эту сторону копать

ВЫБРАТЬ
   "А" КАК Кто,
   "Б" КАК Кому,
   300 КАК Сумма
ПОМЕСТИТЬ ТаблДолгов

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
   "Б",
   "С",
   400
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
   ТаблДолгов.Кто,
   ТаблДолгов.Кому,
   ТаблДолгов.Сумма,
   ТаблДолгов1.Кто КАК Кто1,
   ТаблДолгов1.Кому КАК Кому1,
   ТаблДолгов1.Сумма КАК Сумма1,
   ТаблДолгов2.Кто КАК Кто2,
   ТаблДолгов2.Кому КАК Кому2,
   ТаблДолгов2.Сумма КАК Сумма2,
   ЕСТЬNULL(ТаблДолгов2.Кому, ЕСТЬNULL(ТаблДолгов1.Кому, ТаблДолгов.Кому)) КАК ИтогоКому
ИЗ
   ТаблДолгов КАК ТаблДолгов
       ЛЕВОЕ СОЕДИНЕНИЕ ТаблДолгов КАК ТаблДолгов1
           ЛЕВОЕ СОЕДИНЕНИЕ ТаблДолгов КАК ТаблДолгов2
           ПО ТаблДолгов1.Кому = ТаблДолгов2.Кто
       ПО ТаблДолгов.Кому = ТаблДолгов1.Кто

Может все-таки стоит начать с общего алгоритма, с идеи так сказать? :))

(16) какая разница кому ? сумма минусов равна сумме плюсов. каждый должник платит свою задолженность ЛЮБОМУ кредитору.

всё это чистая математика, ни один суд таких расчетов не примет :)

(34) Да ты чо, правда что ли?
То есть А должна меньше на 100 рублей неважно кому и получила 100 рублей неважно от кого? :)))

(35) именно так. и после платежа задолженность обоих изменяется.

всё равно это применимо только к платежам внутри холдинга.

По условию задачи организации расчитаются в ноль? или не обязательно?

(36) Задолженность - это всегда _кто_ и _кому_.
Разве нет?
Как по-твоему трансформируется таблица из (0)? Последовательный алгоритм можно? :))

(38) не обязательно

(38) LOL
Если бы в ноль, то просто все платят всем и всё :))

(39) мне нравится способ из (14)

(42) А разве в (14) не ерунда написана? :))

Нахождением кратчайшего пути графа пахнет. ;)

нет. в любой базе сумма дебета равна сумме кредита. даже если ето торговля и проводок вообще нет.

(43) разъясни мне, что я ошибаюсь. а то ты только многозначительно улыбаться можешь пока

(41) лол, не все и всем, а сокращаем и получаем, кто кому остался.

(43) в (14) написана не ерунда, а сам факт - организация является дебитором или кредитором. это единственная задача, которую можно решить запросом. а на счет нарастающего итога, если организаций будет 10 и между каждыми из них будет долг, тогда порядок погашения без нарастающего итога/рекурсии врядли обойтись.

(46) Да на уровне определения того, кто сколько должен дать и взять без определения кому все просто :))
При взаимозачете после всех манипуляций каждый должен заплатить столько же, сколько заплатят ему.
Таким образом, считаем в разрезе по организациям, кто сколько заплатил и сколько получил.
Каждая организация должна заплатить минимум из этих двух сумм :))

А вот кому, это уже интересно :))

(47) Что значит "организации расчитаются в ноль"?

(48) В (14) вообще непонятно что написано. Что решается в (14)?

(49) не вижу отличий от (14)

(51) "организация является дебитором или кредитором"

(53) Зачем?

(53)+ фактически получается после этого в общак кидают все кто кредитор, и из общака забирают все кто кредитор. в итоге в общаке "0" останется

(55)+ *в общак кидают все кто дебитор

(55) и я про то же

(52) Где в (14) 300?
Именно эту сумму можно заплатить по кругу и погасить взаимных долгов на эту сумму.

(55) Да это круто, но кто кому сколько после этого должен? :))

(50 как в данном пример) А = - 200 В = 100 С = 100
Когда В и С заплатят А в итоге никто никому не останется должен.

А если А было бы долнжо В - 400.

(59) а какая разница кто кому сколько должен? сам факт, ты должен, значит давай денег. так в любых "играх" решается

Пример 2:
Орг1| Орг2| Долг
А   | B   | 300
B   | C   | 400
C   | D   | 500
D   | E   | 300
E   | A   | 600

Сворачиваем таблицу методом (14) получаем:  А  300
                                           В -100
                                           С -100
                                           D  200
                                           E -300
По хорошему Е отдаёт А 300, В и С отдают D по 100 ( это будет кратчайший путь) , но
можно и так Е отдаст D 200, потом Е отдаст А 100, а потом B и С отдадут А ещё по сто ( это не оптимально), вот и требуется определить кто и кому должен отдать наиболее оптимально

А, пардоньте :))
Задача изощреннее, чем я думал, хотя смысл не меняется :))
Нужно взять все платежи и вычесть из них взаимозачеты :))
Таким образом, задача та же, нужно взаимозачеты разложить по получателям.
Разве нет?

(63) ага

это две задачи в одной

(64) Ну тогда значит да, задача та же, как определить суммы взаимозачетов с определением того, кто кому сколько должен заплатить :))

(62) давай расскажи критерий "кратчайшего пути".

(65) Это три :))
1. Определить суммы платежей каждой компании в рамках взаимозачетов.
2. Разбить полученные в 1 суммы на получателей.
3. Вычесть из начальных платежей платежи, полученные в 2, это и есть необходимые платежи :))

(66) а нафига? вот я ща напишу любые суммы хоть по рублю и пусть скажут что я не прав.

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

(67) Минимальное количество платежей, разве нет?

(69) Ты о чем?

(70) >>следующего должника
Какого именно? :))

(71) или минимальная сумма? или расстяние между плательщиками?

хотя протелепатировал ты логично

разделить на две таблицы должников и получателей, а потом связать по Минмальной разнице между модулями чисел.

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

(76) ну вот тут и всплыл нарастающий итог.

(62) Я бы делал так:
1. Свертка (14)
2. Поиск одинаковых по модулю и разных по знаку сумм и закрытие их.
3. Отсортировать что осталось по убыванию модуля.
4. Брать первую отрицательную сумму и гасить положительные как в (70)

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

Можно упростить и элементы бреда но все же

ВЫБРАТЬ
   ВЫБОР
       КОГДА ВложенныйЗапрос.СуммаДолга < 0
           ТОГДА NULL
       ИНАЧЕ ВложенныйЗапрос.Кому
   КОНЕЦ КАК Кому,
   ВЫБОР
       КОГДА (НЕ ВложенныйЗапрос.СуммаДолга < 0)
           ТОГДА NULL
       ИНАЧЕ ВложенныйЗапрос.Кому
   КОНЕЦ КАК Кто,
   ВЫБОР
       КОГДА (НЕ ВложенныйЗапрос.СуммаДолга < 0)
           ТОГДА ВложенныйЗапрос.СуммаДолга
       ИНАЧЕ -ВложенныйЗапрос.СуммаДолга
   КОНЕЦ КАК Сколько
ИЗ
   (ВЫБРАТЬ
       ВложенныйЗапрос.Кому КАК Кому,
       СУММА(ВложенныйЗапрос.СуммаДолга) КАК СуммаДолга
   ИЗ
       (ВЫБРАТЬ
           ВложенныйЗапрос.Кому КАК Кому,
           ВложенныйЗапрос.СуммаДолга КАК СуммаДолга
       ИЗ
           (ВЫБРАТЬ
               ТаблицаИсходныхДанных.Кто КАК Кому,
               СУММА(-ТаблицаИсходныхДанных.Сумма) КАК СуммаДолга
           ИЗ
               (ВЫБРАТЬ
                   "A" КАК Кто,
                   "B" КАК Кому,
                   300 КАК Сумма
               
               ОБЪЕДИНИТЬ
               
               ВЫБРАТЬ
                   "B",
                   "C",
                   400
               
               ОБЪЕДИНИТЬ
               
               ВЫБРАТЬ
                   "C",
                   "A",
                   500) КАК ТаблицаИсходныхДанных
           
           СГРУППИРОВАТЬ ПО
               ТаблицаИсходныхДанных.Кто
           
           ОБЪЕДИНИТЬ ВСЕ
           
           ВЫБРАТЬ
               ТаблицаИсходныхДанных.Кому,
               СУММА(ТаблицаИсходныхДанных.Сумма)
           ИЗ
               (ВЫБРАТЬ
                   "A" КАК Кто,
                   "B" КАК Кому,
                   300 КАК Сумма
               
               ОБЪЕДИНИТЬ
               
               ВЫБРАТЬ
                   "B",
                   "C",
                   400
               
               ОБЪЕДИНИТЬ
               
               ВЫБРАТЬ
                   "C",
                   "A",
                   500) КАК ТаблицаИсходныхДанных
           
           СГРУППИРОВАТЬ ПО
               ТаблицаИсходныхДанных.Кому) КАК ВложенныйЗапрос) КАК ВложенныйЗапрос
   
   СГРУППИРОВАТЬ ПО
       ВложенныйЗапрос.Кому) КАК ВложенныйЗапрос

ВЫБРАТЬ
   Т.Орг1,
   Т.Орг2,
   Т.Долг
ПОМЕСТИТЬ Табл
ИЗ
   &ТЗ КАК Т
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
   Т1.Орг1 КАК Плательщик,
   Т1.Орг2 КАК Получатель,
   ВЫБОР КОГДА (Т1.Долг <= Т2.Долг) И (Т1.Долг <= Т3.Долг) Тогда Т1.Долг
   ИНАЧЕ
   ВЫБОР КОГДА (Т2.Долг <= Т3.Долг) И (Т2.Долг <= Т1.Долг) Тогда Т2.Долг
   ИНАЧЕ Т3.Долг Конец КОНЕЦ КАК СуммаВзаиморасчетов
ИЗ
   Табл КАК Т1
Левое Соединение Табл КАК Т2
ПО Т1.Орг2 = Т2.Орг1
Левое Соединение Табл КАК Т3
ПО Т2.Орг2 = Т3.Орг1
ГДЕ (Т1.Орг1 = Т3.Орг2) ИЛИ (Т1.Орг1 = Т2.Орг2 И Т1.Орг2 = Т3.Орг2)


Этот запрос работает для цепочек не более чем из трех организаций (для большего числа - больше соединений и условий).
Умеет отсеивать не замкнутые цепочки. Умеет считать более короткие цепочки.

Проверил в обработке - вроде работает.

Спасибо, за 10 данных минут я бы её явно не осилил, так что я спокоен ))

(80) упс

ВЫБРАТЬ
   "А" КАК Орг1,
   "Б" КАК Орг2,
   300 КАК Долг
ПОМЕСТИТЬ Табл

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
   "Б",
   "В",
   400

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
   "В",
   "А",
   500

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
   "В",
   "Б",
   100

(82) И запрос из (80) посчитал правильно.
АБ - 300
БВ - 300
БВ - 100
ВА - 300
ВБ - 100

Это правильно.

(83) разве?

АБ - 300
БВ - 300
-----------
АВ - 300

(85) В (82) написано, что "В" должен "А" - 500.

Ты что то путаешь. Требуется погасить долги (деньгами или документами), а не убрать "посредников".

+(86) Я понял задачу так. Хотя можно и "посредников" убирать.

(86) И что по-твоему означает "оптимальный путь погашения долга организациями"?

(83)
какие посредники??
БВ - 100
ВБ - 100
встретились и дали друг дружке по 100 рублей. зато в кафе посидели.

(87) Тогда из 4 итераций ты сделал 5

(88)(89)(90) Как должно быть на основании (82)?

(90) Можно добавить в запросе СГРУППИРОВАТЬ.

(91) Должна быть одна запись
ВА - 200

(91) В должна А 200 :))

(93)(94) А "Б" "В" ничего не должно. Было должно - 400.

(95) Не 400, а 300 с учетом последнего объединения. И что?

Н совсем понимаю - что означает запись из (93) "В должна А 200 :))" - это остаток всех долгов между организациями или это значит, что "В" должна перечислить "А" 200? А что с остальными?

(97) Это означает, что все остальные долги можно закрыть взаимозачетами.

(98) Понятно. Говорили о разном. Все о остатках взаиморасчетов, а я о суммах зачетов.

+(99) Т.е. мой запрос решает задаче - какие платежи надо произвести между организациями (или оформить документы), что бы все остались "при своих" (имею ввиду деньгах) - это распространенная задача.

(100) Для ограниченного числа организаций не интересно :))

(101) Цепочки дружественных организаций всегда ограничены.

(102) Ну да, например 50 штук.
И какой будет запрос? :))