如何在oracle中找到最接近的子集总和

我有两个表： 1）其中一个用于发票，有成千上万的数据。在我的INVOICES表中，有发票和它们的价格给顾客。 2）另一个是债务。在我的DEBTS表中，每个客户都有发票的全部债务。
我的目标是找到最近的款项和债务的发票。举例来说，我有表：如何在oracle中找到最接近的子集总和

债项表：

CUSTOMER_ID   TOTAL_DEBTS 
     3326660    444$  
     2789514    165$  
     4931541    121$

发票表：

CUSTOMER_ID  INVOICE_ID  AMOUNT_OF_INVOICE 
    3326660    1a     157$ 
    3326660    1b     112$ 
    3326660    1c     10$ 
    3326660    1d     94$ 
    3326660    1e     47$ 
    3326660    1f     35$ 
    3326660    1g     14$ 
    3326660    1h     132$ 
    3326660    1i     8$ 
    3326660    1j     60$ 
    3326660    1k     42$ 
    2789514    2a     86$ 
    2789514    2b     81$ 
    2789514    2c     99$ 
    2789514    2d     61$ 
    2789514    2e     16$ 
    2789514    2f     83$ 
    4931541    3a     11$ 
    4931541    3b     14$ 
    4931541    3c     17$ 
    4931541    3d     121$ 
    4931541    3e     35$ 
    4931541    3f     29$

我的目标表：

CUSTOMER_ID  TOTAL_DEBTS  CALCULATED_AMOUNT  INVOICES_ID 
    3326660    444$    444$    1a,1b,1f,1h,1i  
    2789514    165$    164$     2b,2f 
    4931541    121$    121$     3d

，因为我的桌子上有数以千计的数据，对我来说性能非常重要。我发现从代码覆盖： closest subset sum

但是，性能低。当我在calculeted_amount和total_debts之间找到相同的值时，我必须停止加法循环。

谢谢你的帮助。

来源

2017-04-11 Abdullah

这不适合SQL的问题。您需要概括所有可能的组合并查看哪一个最接近。 –

同意@GordonLinoff，阅读它，它可以帮助你理解你对[wiki]的问题（https://en.wikipedia.org/wiki/Subset_sum_problem） – Seyran

使用递归查询：

^demo

with 
    t1 as ( 
     select customer_id cid, total_debts dbt, invoice_id iid, amount_of_invoice amt, 
       row_number() over (partition by customer_id order by invoice_id) rn 
      from debts d join invoices i using (customer_id)), 
    t2 (cid, iid, ams, dbt, amt, sma, rn) as ( 
     select cid, cast(iid as varchar2(4000)), cast(amt as varchar2(4000)), 
       dbt, amt, amt, rn 
      from t1 
     union all 
     select t2.cid, 
       t2.iid || ', ' || t1.iid, 
       t2.ams || ', ' || t1.amt, 
       t2.dbt, t2.amt, t1.amt + t2.sma, t1.rn 
      from t2 
      join t1 on t1.cid = t2.cid and t1.rn > t2.rn and t2.sma + t1.amt <= t1.dbt), 
    t3 as (
     select t2.*, rank() over (partition by cid order by dbt - sma) rnk 
      from t2) 
select cid, iid, ams, dbt, sma from t3 where rnk = 1

输出：

CID IID       AMS        DBT  SMA   
------- ---------------------------- ------------------------------ -------- -------- 
2789514 2b, 2f      81, 83        165  164 
3326660 1a, 1d, 1e, 1g, 1h   157, 94, 47, 14, 132     444  444 
3326660 1b, 1c, 1d, 1e, 1f, 1g, 1h 112, 10, 94, 47, 35, 14, 132   444  444 
3326660 1a, 1c, 1f, 1h, 1i, 1j, 1k 157, 10, 35, 132, 8, 60, 42   444  444 
3326660 1a, 1b, 1f, 1h, 1i   157, 112, 35, 132, 8     444  444 
4931541 3d       121         121  121 

6 rows selected

子查询T1连接两个表，并增加了用于未来数据合并列rn。 T2是分层的，它完成了工作的主要部分 - 结合所有数据直到达到债务。 T3使用功能rank过滤最佳解决方案。正如你所看到的CID 3326660有四种最好的组合。

对于大量的数据递归子查询很慢，并且此解决方案不起作用，请注意。

来源

2017-04-11 12:50:35

如何在oracle中找到最接近的子集总和

回答

相关问题