Эффективно выберите строки из 2 DataTables соответствующих сумму для столбца

Question

У меня 2 DataTables:

1. : Кредиторская задолженность содержит набор счетов-фактур, которые я должен заплатить. (InvNo-Amount)
2. Дебиторская задолженность: содержит набор счетов-фактур, которые я должен получить. (InvNo-сумма)

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

Пример:

Payables  Receivables 
--------  ----------- 
INV1 120  ABC1 100 
INV2 50  ABC2 30 
INV3 80  ABC3 20 
INV4 30  ABC4 70 

Я могу создать комбинацию (INV1 + INV2 + INV4 = 200) & (ABC1 + ABC2 + ABC4 = 200), так что оба матча.

идея которая у меня есть для реализации является:

1. Найти счета-фактуры с одинаковым количеством из обоего таблиц & выбрать их.
2. Найти изделие с максимальной суммой из любой таблицы. Постарайтесь сопоставить эту сумму, выбирая строки (один или несколько) из другой таблицы.

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

Answer 1

См. knapsack problem.

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

Что-то вроде этого:

def knapsack(items) { 
    sums = {0: null} 
    for item in items: 
    for sum, last_item in sum: 
     // Skip if you've already used item or the you can get the sum some other way. 
     if last_item == item or sum + item.value in sums: continue 
     else: 
     sums[sum+item.value] = item   
    return sums 

payable_sums = knapsack(payables) 
receivable_sums = knapsack(receivables) 
for sum, item in payable_sums: 
    if sum in receivable_sums: 
     print "Success, you can get ", sum, " on both sides." 

Если вам необходимо получить фактические элементы просто использовать значение в картах для определения последнего пункта, вычесть значение элемента и повторять за оставшуюся сумму до вас достигают 0.

Алгоритм всегда даст вам результат (по крайней мере, с двух сторон).

Answer 2

Эта проблема очень похожа на subset sum problem.

Кредиторская задолженность может быть представлена ​​в виде отрицательных значений, и дебиторской задолженности как положительный, а затем вам нужно найти непустое множество, суммирующий 0.

Если вы хотите сделать изменения knapsack, вы можете реализовать очень эффективное решение проблемы с рюкзаком с dynamic programming, для каждой таблицы отдельно, а затем запросить полученную матрицу для размеров ранца, которые имеют одинаковое значение для кредиторской и дебиторской задолженности.