In SQL find the combination of rows whose sum add up to a specific amount (or amt in other table)
Table_1
D_ID Integer Deposit_amt integerTable_开发者_C百科2
Total_ID Total_amt integer
Is it possible to write a select statement to find all the rows in Table_1 whose Deposit_amt sum to the Total_amt in Table_2. There are multiple rows in both tables.
Say the first row in Table_2 has a Total_amt=100. I would want to know that in Table_1 the rows with D_ID 2, 6, 12 summed = 100, the rows D_ID 2, 3, 42 summed = 100, etc.
Help appreciated. Let me know if I need to clarify.
I am asking this question as someone as part of their job has a list of transactions and a list of totals, she needs to find the possible list of transactions that could have created the total. I agree this sounds dangerous as finding a combination of transactions that sums to a total does not guarantee that they created the total.
I wasn't aware it is an np-complete problem.
Give your friend this, and wish her good luck .. :p
Just for fun I did a brute force solution. It will find combinations of one, two, or three records that add up to Total_amt. You could expand it to handle more transactions per sum, by adding d4, d5 subselects, etc.:
begin tran
create table Table_1 (D_ID int, Deposit_amt int)
create table Table_2 (Total_ID int, Total_amt int)
insert into Table_1 (D_ID, Deposit_amt) values (1, 4)
insert into Table_1 (D_ID, Deposit_amt) values (2, 3)
insert into Table_1 (D_ID, Deposit_amt) values (3, 1)
insert into Table_1 (D_ID, Deposit_amt) values (4, 1)
insert into Table_1 (D_ID, Deposit_amt) values (5, 9)
insert into Table_1 (D_ID, Deposit_amt) values (6, 13)
insert into Table_1 (D_ID, Deposit_amt) values (7, 6)
insert into Table_1 (D_ID, Deposit_amt) values (8, 7)
insert into Table_1 (D_ID, Deposit_amt) values (9, 12)
insert into Table_1 (D_ID, Deposit_amt) values (10, 4)
insert into Table_2 (Total_ID, Total_amt) values (1, 17)
insert into Table_2 (Total_ID, Total_amt) values (2, 23)
insert into Table_2 (Total_ID, Total_amt) values (3, 55)
insert into Table_2 (Total_ID, Total_amt) values (4, 4)
select t.Total_amt,
d1.D_ID as d1_ID, d1.Deposit_amt as d1_amt,
d2.D_ID as d2_ID, d2.Deposit_amt as d2_amt,
d3.D_ID as d3_ID, d3.Deposit_amt as d3_amt
from Table_2 t
cross join (
select D_ID, Deposit_amt from Table_1
) d1
inner join (
select D_ID, Deposit_amt from Table_1
union all
select null, null
) d2 on d1.D_ID > d2.D_ID or d2.D_ID is null
inner join (
select D_ID, Deposit_amt from Table_1
union all
select null, null
) d3 on d2.D_ID > d3.D_ID or d3.D_ID is null
where isnull(d1.Deposit_amt, 0) + isnull(d2.Deposit_amt, 0) + isnull(d3.Deposit_amt, 0) = t.Total_amt
order by Total_amt
rollback tran
Output:
Total_amt d1_ID d1_amt d2_ID d2_amt d3_ID d3_amt
----------- ----------- ----------- ----------- ----------- ----------- -----------
4 3 1 2 3 NULL NULL
4 4 1 2 3 NULL NULL
4 1 4 NULL NULL NULL NULL
4 10 4 NULL NULL NULL NULL
17 9 12 3 1 1 4
17 9 12 4 1 1 4
17 10 4 5 9 1 4
17 8 7 7 6 1 4
17 6 13 1 4 NULL NULL
17 10 4 6 13 NULL NULL
17 10 4 8 7 7 6
17 8 7 5 9 4 1
17 10 4 9 12 4 1
17 8 7 5 9 3 1
17 10 4 9 12 3 1
17 6 13 3 1 2 3
17 6 13 4 1 2 3
23 8 7 6 13 2 3
23 6 13 5 9 3 1
23 6 13 5 9 4 1
23 10 4 7 6 6 13
23 10 4 9 12 8 7
23 7 6 6 13 1 4
23 9 12 8 7 1 4
(24 row(s) affected)
Note: You could filter out individual rows whose Deposit_amt > Total_amt, but this would probably not help performance much unless Deposit_amt was indexed.
CREATE TABLE #N1 (ID INT NOT NULL IDENTITY(1,1) PRIMARY KEY CLUSTERED, Val INT)
CREATE TABLE #N2 (ID INT NOT NULL IDENTITY(1,1) PRIMARY KEY CLUSTERED, Val INT)
-- SELECT TOP 20 'INSERT INTO #N1 (Val) VALUES (' + CAST (CAST (RAND (CAST (NEWID () AS VARBINARY) ) * 100 AS INT) AS VARCHAR) + ')' FROM sys.objects
INSERT INTO #N1 (Val) VALUES (93)
INSERT INTO #N1 (Val) VALUES (93)
INSERT INTO #N1 (Val) VALUES (86)
INSERT INTO #N1 (Val) VALUES (23)
INSERT INTO #N1 (Val) VALUES (51)
INSERT INTO #N1 (Val) VALUES (85)
INSERT INTO #N1 (Val) VALUES (93)
INSERT INTO #N1 (Val) VALUES (27)
INSERT INTO #N1 (Val) VALUES (12)
INSERT INTO #N1 (Val) VALUES (15)
INSERT INTO #N1 (Val) VALUES (23)
INSERT INTO #N1 (Val) VALUES (87)
INSERT INTO #N1 (Val) VALUES (94)
INSERT INTO #N1 (Val) VALUES (61)
INSERT INTO #N1 (Val) VALUES (15)
INSERT INTO #N1 (Val) VALUES (86)
INSERT INTO #N1 (Val) VALUES (38)
INSERT INTO #N1 (Val) VALUES (81)
INSERT INTO #N1 (Val) VALUES (67)
INSERT INTO #N1 (Val) VALUES (45)
-- SELECT TOP 20 'INSERT INTO #N2 (Val) VALUES (' + CAST (CAST (RAND (CAST (NEWID () AS VARBINARY) ) * 100 AS INT) AS VARCHAR) + ')' FROM sys.objects
INSERT INTO #N2 (Val) VALUES (32)
INSERT INTO #N2 (Val) VALUES (1)
INSERT INTO #N2 (Val) VALUES (24)
INSERT INTO #N2 (Val) VALUES (20)
INSERT INTO #N2 (Val) VALUES (40)
INSERT INTO #N2 (Val) VALUES (25)
INSERT INTO #N2 (Val) VALUES (37)
INSERT INTO #N2 (Val) VALUES (19)
INSERT INTO #N2 (Val) VALUES (47)
INSERT INTO #N2 (Val) VALUES (23)
INSERT INTO #N2 (Val) VALUES (7)
INSERT INTO #N2 (Val) VALUES (53)
INSERT INTO #N2 (Val) VALUES (75)
INSERT INTO #N2 (Val) VALUES (82)
INSERT INTO #N2 (Val) VALUES (15)
INSERT INTO #N2 (Val) VALUES (26)
INSERT INTO #N2 (Val) VALUES (22)
INSERT INTO #N2 (Val) VALUES (70)
INSERT INTO #N2 (Val) VALUES (17)
INSERT INTO #N2 (Val) VALUES (1)
SELECT #N1.ID, #N2.ID, t.Val1, t.Val2
FROM (
SELECT
#N1.Val AS Val1
, #N2.Val AS Val2
FROM #N1,#N2
WHERE #N1.Val+#N2.Val=100
) AS t
INNER JOIN #N1 ON #N1.Val = t.Val1
INNER JOIN #N2 ON #N2.Val = t.Val2
This is my approach in Oracle PLSQL,
select *
from Table_2 tt
cross join
(
select
a.deposit_amt as dep_one,
b.deposit_amt as dep_two,
c.deposit_amt as dep_three
from Table_1 a
inner join (select * from Table_1 union all select null , null from dual)b
on b.deposit_amt < a.deposit_amt
or b.deposit_amt is null
inner join (select * from Table_1 union all select null , null from dual)c
on c.deposit_amt < b.deposit_amt
or c.deposit_amt is null
order by 1,2,3 asc
) p
where nvl(dep_one,0) + nvl(dep_two,0) + nvl(dep_three,0) = tt.total_amt
order by tt.total_amt
加载中,请稍侯......
精彩评论