Подбор под сумму

Задана сумма. Нужно подобрать значения из списка, так, чтобы их сумма совпадала с заданной.

Решение для Oracle

WITH t AS (
	SELECT /*+ materialize */
	rownum rn, id, doc_sum sm
	FROM OPERATIONS s 
	ORDER BY sm desc, id desc
)
SELECT trim(',' FROM t1.PATH) ids, sum(t2.sm) sm
FROM t t2
JOIN ( 
	SELECT 
	sm, id, rn, LEVEL lvl, SYS_CONNECT_BY_PATH(id,',') PATH
	FROM t
	START WITH sm <= :sum
	CONNECT BY PRIOR rn > rn
) t1 ON regexp_like(t1.PATH||',',','||t2.id||',')
GROUP BY path
having sum(t2.sm) = :sum

Решение для PostgreSQL

WITH RECURSIVE t AS (
	with q as (
		select 
		row_number() over (order by sm desc, id desc) rn
		, id
		, sm
		from OPERATIONS
		where sm <= :sum::numeric
	) 
    SELECT id,
    	rn,
        sm,
        sm tsm,
        id::text AS path
       FROM q
    UNION ALL
     SELECT q.id AS id,
     	q.rn,
        q.sm AS sm,
        t.tsm + q.sm AS tsm,
        (t.path || ','::text) || q.id AS path
       FROM t
         JOIN q ON q.rn < t.rn
    )
 SELECT t.path
   FROM t
  WHERE t.tsm = :sum::numeric
 LIMIT 1;
Опубликовано 16.10.2016