Tukukkk

I have a table that is like below, as example

A.    1

B.    2

C.    3

D.    99

E.    90

I need a query that calculates and returns the set of the greatest number of rows that sum to equal or less than 102, for example, choosing the set with the total nearest to the target.

If there are tied results that have the same total and same number of rows then take the set with the highest single value of Accessible

In this example the answer is A,B,D because that has three items, while C,D (which also sums to 102) only has two.

You could use a recursive query, but as this is a non-polynomial problem, the performance will degrade with more records. The first with query is just generating the sample data. In your case you would of course query your actual table:

with tbl(key, value) as (

    select 'A',  1 from dual union all

    select 'B',  2 from dual union all

    select 'C',  3 from dual union all

    select 'D', 99 from dual union all

    select 'E', 90 from dual

),

rec(greatest_key, greatest_single, key_count, keys, total) as (

    select     key,

               value,

               1,

               key, 

               value

    from       tbl

    union all

    select     tbl.key,

               greatest(tbl.value, rec.greatest_single),

               rec.key_count+1,

               substr(rec.keys, 0, 1000) || ', ' || tbl.key,

               rec.total + tbl.value

    from       rec 

    inner join tbl 

            on tbl.key > rec.greatest_key

           and rec.total + tbl.value <= 102

),

ordered(total, keys, r) as (

    select   total, keys, row_number() over ( 

                          order by total desc, key_count desc, greatest_single desc)

    from     rec

)

select total, keys

from   ordered

where  r = 1

The ordered part is only there to get the "top" record.

See it run on rextester.

If you have Oracle 12c+ you can end the query without using ordered:

select   total, keys

from     rec

order by total desc, 

         key_count desc

OFFSET 0 ROWS FETCH NEXT 1 ROWS ONLY 

Here is my attempt. NOT TESTED.

FUNCTION find_min_set ( p_target IN NUMBER ) RETURN VARCHAR2 IS

  CURSOR c1 ( p_find_val NUMBER ) IS

    SELECT the_id, the_val

    FROM   the_table t1

    WHERE  the_val = ( SELECT MAX( the_val ) the_val

                       FROM   the_table

                       WHERE  the_val <= p_find_val ) ;

  l_target NUMBER;

  l_id     VARCHAR2(16);

  l_val    NUMBER;

  l_ret_List  VARCHAR2(4000) := '';

BEGIN

   l_target := p_target;

   WHILE l_target > 0 LOOP

      OPEN c1 ( l_target );

      FETCH c1 INTO l_id, l_val;

      EXIT WHEN c1%NOTFOUND;

      CLOSE c1;

      l_ret_list := l_ret_list || ' ' || l_id;

      l_target := l_target - l_val;

   END LOOP;

   l_ret_list := 'Target: ' || p_target || ',' ||

                  'Remaidner: ' || l_target ||  ', ' ||

                  'List: ' || l_ret_list;

   RETURN ( l_ret_list );

END;

/

The query returns the col with the largest value <= the target.
The returned value is subtracted from the target and we serach again for teh largest value <= the new target.
We repeat this until the new target is 0 (original tager has been reached) or theer are no more values <= target.
Form teh results as required and return.