找出最小匹配对 [英] Find out minimum matching pairs

问题描述

我有2个列表，具有相同的对象和3个属性(accNo、accType&；Balance)。

List<> CSList
'CS1', 'CS', 3000
'CS2', 'CS', 2000   
'CS3', 'CS', 1000   

List<> CLList
'CL1', 'CL', 4000   
'CL2', 'CL', 500    
'CL3', 'CL', 1000

在我的示例余额总和中，所有acctype = CS(3000+2000+1000=6000)将始终大于或等于acctype = CL(4000+500+1000=5500)。

我正在尝试按CS余额结清我的CL余额。例如，帐户CL1的余额为4000，可由CS1 & CS3(3000+1000)或CS1 & CS2(3000+1000(CS2 remaining balance 1000 can be used next))结清。

我想找出使CL帐户余额0通过CS帐户(首选输出2)的最低交易集数量。

Possible output 1:

Debit       Credit      Amount
CS1         CL1         3000
CS2         CL1         1000
CS2         CL2         500
CS2         CL3         500
CS3         CL3         500


Possible output 2:

Debit       Credit      Amount
CS1         CL1         3000
CS3         CL1         1000
CS2         CL2         500
CS2         CL3         1000

推荐答案

贪婪的方法不会产生此问题的最佳结果。 寻找最优交易数量的解决方案：

1. CL帐户发电机组
   例如((CL1，CL2，CL3)，(CL1，CL2)，(CL1，CL3)，(CL2，CL3)，(CL1)，(CL2)，(CL3))
2. 对于每个子集，选择大于子集CL帐户金额总和的所有CS帐户。
3. 对于每个选中的CS账户，从选中的CS账户中减去子集CL账户的金额之和
4. 对于剩余的CL帐户，重复步骤1至3，直到完成所有CL帐户扣减

如果您有M个CS帐户和N个CL帐户，则复杂性可能为O(M^N*2^N2)

这篇关于找出最小匹配对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！