Suppose I have the following dataset named "Num":
80
70
50
40
20
20
20
10
I would like to add these numbers up into the least number of groupings that are less than (or equal to) 100. Each number can be used only once. So for the example above we would group as follows:
Group 1: 80 + 20
Group 2: 70 + 20 + 10
Group 3: 50 + 40
Group 4: 20
And my answer would be 4 (4 unique groupings as close to & including 100).
WITH
num AS
(
SELECT 80 "NUMBERS" FROM DUAL UNION ALL SELECT 70 "NUMBERS" FROM DUAL UNION ALL SELECT 50 "NUMBERS" FROM DUAL UNION ALL SELECT 40 "NUMBERS" FROM DUAL UNION ALL
SELECT 20 "NUMBERS" FROM DUAL UNION ALL SELECT 20 "NUMBERS" FROM DUAL UNION ALL SELECT 20 "NUMBERS" FROM DUAL UNION ALL SELECT 10 "NUMBERS" FROM DUAL
),
grid AS
( SELECT ROW_NUMBER() OVER(ORDER BY NUMBERS DESC) "ID", NUMBERS "NUM" FROM num ),
add_0 AS
(
SELECT
ROW_NUMBER() OVER(ORDER BY g0.ID ASC, g1.ID DESC, g2.ID DESC) "INDX",
g0.ID "ID0",
g0.NUM "NUM0",
g1.ID "ID1",
g1.NUM "NUM1",
g0.NUM + g1.NUM "RESULT0",
g2.ID "ID2",
g2.NUM "NUM2",
g0.NUM + g1.NUM + g2.NUM "RESULT1"
FROM
grid g0
INNER JOIN
grid g1 ON(g1.ID > g0.ID)
INNER JOIN
grid g2 ON(g2.ID > g0.ID)
WHERE
g0.NUM + g1.NUM <= 100 OR
g0.NUM + g1.NUM + g2.NUM <= 100
ORDER BY g0.ID, g1.ID, g2.ID
),
calc AS
(
SELECT
ROW_NUMBER() OVER(PARTITION BY ID0 ORDER BY ID0, ID1, ID2) "ORD",
ID0,
CASE WHEN ID1 = ID2 THEN 0 ELSE ID1 END "ID1",
CASE
WHEN ID1 = ID2 THEN 0
WHEN CASE WHEN RESULT0 = 100 THEN 0 ELSE CASE WHEN RESULT1 <= 100 THEN RESULT1 ELSE 0 END END <
CASE
WHEN CASE WHEN RESULT0 = 100 THEN 0 ELSE CASE WHEN RESULT1 <= 100 THEN RESULT1 ELSE 0 END END > RESULT0 THEN 0
ELSE
RESULT0
END THEN 0
ELSE
CASE
WHEN ID1 = ID2 THEN 0
WHEN RESULT0 = 100 THEN 0
WHEN RESULT1 = 100 THEN ID2
WHEN RESULT0 > RESULT1 THEN 0
WHEN RESULT0 <= RESULT1 THEN ID2
ELSE
Nvl(ID2,0)
END
END "ID2",
--
NUM0,
CASE WHEN ID1 = ID2 THEN 0 ELSE NUM1 END "NUM1",
CASE
WHEN CASE WHEN RESULT0 = 100 THEN 0 ELSE CASE WHEN RESULT1 <= 100 THEN RESULT1 ELSE 0 END END <
CASE
WHEN CASE WHEN RESULT0 = 100 THEN 0 ELSE CASE WHEN RESULT1 <= 100 THEN RESULT1 ELSE 0 END END > RESULT0 THEN 0
ELSE
RESULT0
END THEN 0
ELSE
CASE
WHEN ID1 = ID2 THEN 0
WHEN RESULT0 = 100 THEN 0
WHEN RESULT1 = 100 THEN NUM2
WHEN RESULT0 > RESULT1 THEN 0
WHEN RESULT0 <= RESULT1 THEN NUM2
ELSE
Nvl(NUM2,0)
END
END "NUM2",
--
CASE
WHEN CASE WHEN RESULT0 = 100 THEN 0 ELSE CASE WHEN ID1 = ID2 THEN 0 WHEN RESULT1 <= 100 THEN RESULT1 ELSE 0 END END > RESULT0 THEN 0
ELSE
RESULT0
END "RESULT0",
CASE WHEN RESULT0 = 100 THEN 0 ELSE CASE WHEN ID1 = ID2 THEN 0 WHEN RESULT1 <= 100 THEN RESULT1 ELSE 0 END END "RESULT1"
FROM
add_0 a
WHERE
ID1 <> ID2
ORDER BY
ID0, ID1,
CASE
WHEN RESULT0 = 100 THEN 0
WHEN RESULT1 = 100 THEN ID2
WHEN RESULT0 > RESULT1 THEN 0
WHEN RESULT0 <= RESULT1 THEN ID2
ELSE
Nvl(ID2,0)
END,
ORD
),
a1 AS
(
SELECT
ID0 "ID0", ID1 "ID1", ID2 "ID2",
NUM0 "NUM0", NUM1 "NUM1", NUM2 "NUM2", RESULT0 + RESULT1 "RESULT"
FROM
calc
WHERE
ROWNUM = 1
),
a2 AS
(
SELECT
ID0 "ID0", ID1 "ID1", ID2 "ID2",
NUM0 "NUM0", NUM1 "NUM1", NUM2 "NUM2", RESULT0 + RESULT1 "RESULT"
FROM
calc
WHERE
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a1), ID0) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a1), ID1) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a1), ID2) = 0 And
RESULT0 + RESULT1 = (SELECT Max(RESULT0+RESULT1) From calc WHERE ID0 = 2) And
ROWNUM = 1
),
a3 AS
(
SELECT
ID0 "ID0", ID1 "ID1", ID2 "ID2",
NUM0 "NUM0", NUM1 "NUM1", NUM2 "NUM2", RESULT0 + RESULT1 "RESULT"
FROM
calc
WHERE
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a1), ID0) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a1), ID1) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a1), ID2) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a2), ID0) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a2), ID1) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a2), ID2) = 0 And
ROWNUM = 1
),
a4 AS
(
SELECT
grid.ID "ID0", 0 "ID1", 0 "ID2",
grid.NUM "NUM0", 0 "NUM1", 0 "NUM2", grid.NUM "RESULT"
FROM
grid
LEFT JOIN
calc ON(grid.ID = calc.ID0)
WHERE
calc.ID0 Is Null And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a1), grid.ID) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a2), grid.ID) = 0 And
InStr((SELECT ID0 || ID1 || REPLACE(ID2, 0, '') FROM a3), grid.ID) = 0
)
-- --------------------------------------------------------------------------------
SELECT
GRP "GRP",
CASE
WHEN ID1 + ID2 = 0 THEN To_Char(NUM0)
WHEN ID2 = 0 And ID1 <> 0 THEN To_Char(NUM0) || ' + ' || To_Char(NUM1)
WHEN ID2 <> 0 THEN To_Char(NUM0) || ' + ' || To_Char(NUM1) || ' + ' || To_Char(NUM2)
END "MATH",
RESULT "RESULT"
FROM
(
SELECT a1.*, 'Group: 1' "GRP" FROM a1
UNION
SELECT a2.*, 'Group: 2' "GRP" FROM a2
UNION
SELECT a3.*, 'Group: 3' "GRP" FROM a3
UNION
SELECT a4.*, 'Group: 4' "GRP" FROM a4
)