递归地向费用应用付款 SQL 服务器

Question

我在一个 table 中既有收费又有付款。付款是 "applied" 费用，以便将帐户余额归零。没有适用的特定顺序，只要所有费用平衡为零（或大部分）即可。

在我尝试构建的 SP 之后，table 将有两种可能的状态。正如我所说，我不在乎它们如何 "applied" 只要大部分费用的余额为零即可。

CREATE TABLE dbo.Transactions (
TrxID       INT IDENTITY,
TrxType     BIT, -- 1 for Charges, 0 for Payments
TrxDescription  VARCHAR(MAX),
Amount  DECIMAL(13,2),
ApplyTo     INT -- TrxID of the charge to which the payment is "applied"
);

INSERT INTO dbo.Transactions VALUES(1,'Charge1',100,NULL);
INSERT INTO dbo.Transactions VALUES(0,'Payment1',-80,NULL);
INSERT INTO dbo.Transactions VALUES(0,'Payment2',-15,NULL);
INSERT INTO dbo.Transactions VALUES(1,'Charge3',200,NULL);
INSERT INTO dbo.Transactions VALUES(0,'Payment4',-20,NULL);
INSERT INTO dbo.Transactions VALUES(0,'Payment5',-80,NULL);
INSERT INTO dbo.Transactions VALUES(0,'Payment6',-105,NULL);

SELECT * FROM dbo.transactions

SELECT SUM(Amount) FROM dbo.Transactions;
SELECT SUM(Amount) FROM dbo.Transactions WHERE TrxType=1;
SELECT SUM(Amount) FROM dbo.Transactions WHERE TrxType=0;

-- CORRECT APPLICATION
UPDATE dbo.Transactions SET ApplyTo=1 WHERE TrxID IN(2,5)
UPDATE dbo.Transactions SET ApplyTo=4 WHERE TrxID IN(3,6,7)

-- The global balance is zero
SELECT SUM(Amount) FROM dbo.Transactions

-- Both charges have zero balance
SELECT t.*,t.Amount+b.Balance 'Balance'
FROM dbo.Transactions t
OUTER APPLY (SELECT SUM(t2.Amount)Balance
         FROM dbo.Transactions t2
         WHERE t.TrxID=t2.ApplyTo
)b

-- WRONG APPLICATION
UPDATE dbo.Transactions SET ApplyTo=1 WHERE TrxID IN(2,3,5)
UPDATE dbo.Transactions SET ApplyTo=4 WHERE TrxID IN(6,7)

-- The global balance is zero
SELECT SUM(Amount) FROM dbo.Transactions

-- Charges dont have correct balance, as they could be both zero if applied correctly
SELECT t.*,t.Amount+b.Balance 'Balance'
FROM dbo.Transactions t
OUTER APPLY (SELECT SUM(t2.Amount)Balance
         FROM dbo.Transactions t2
         WHERE t.TrxID=t2.ApplyTo
)b

谢谢。

Answer 1

您要解决的是subset sum problem。这是一个NP完全问题，甚至指数时间O(2^N/2).

中最好的算法运行

鉴于您的问题看起来像是一个余额 sheet，可能涉及数以千计的付款和费用（子集和总和），因此没有一个确切的解决方案可以运行合理数量的时间.

这里有一个解决方案，它会尽最大努力使用 MySQL 存储过程应用付款：

BEGIN


    DECLARE charge int;
    declare charge_id int;
    DECLARE payment int;
    declare payment_id int;
    declare foundrows int;

    balance_loop: LOOP

       SELECT trxid, amount into charge_id, charge 
        from transactions 
        where trxtype = 1
        and applyto is null
        limit 1;

        SET foundrows = (SELECT FOUND_ROWS());

        if foundrows = 0 then
            call debug(concat('Finished '));
            leave balance_loop;
        end if;

        call debug(concat('Balancing charge ', charge_id));  
        call debug(concat('starting with charge amount: ', charge));

        payment_loop: while charge > 0 do
            call debug(concat('start charge: ', charge));

            SELECT trxid, ABS(amount) into payment_id, payment
            FROM transactions
            WHERE trxtype =  0
            AND applyto is null
            AND ABS(amount) <= charge
            order by RAND()
            limit 1;


            call debug(concat('applying payment: ', payment));
            set charge = charge - payment;      

            call debug(concat('remaining charge: ', charge));


            if charge >= 0 then
                update transactions 
                set applyto = charge_id
                where trxid = payment_id;               
                call debug(concat('applied payment_id', payment_id, ' to charge ID ', charge_id));
            end if;     

        end while;

        update transactions set applyto = 0 where trxid = charge_id;

    end loop;

END

递归地向费用应用付款 SQL 服务器

Apply payments to charges recursively SQL Server

sql

sql-server

cursor

balance