10-336 行間の差の最大値も取得するナップサック問題

SQLパズル

knapSackTable
sortKey  Val
-------  ---
      1   10
      3  100
      5    1
     10    2
     11    3
     14   10
     16   10
     17    5
     20    6

sortKeyの昇順にソートした順序において
sortKeyが連続している組み合わせの中でValが9未満で最大となる組み合わせを求め、
sortKeyの開始値と終了値と連続したsortKeyの中での差の最大値を求める。

上記の例では、
sortKeyが5,10,11の組み合わせと
sortKeyが20のValの合計が
1+2+3=6で最大となります。

出力結果
rootSortKey  sortKey  sumVal  maxDiff
-----------  -------  ------  -------
          5       11       6        5
         20       20       6        0

こちらを参考にさせていただきました(英語)

データ作成スクリプト

create table knapSackTable(sortKey,Val) as
select  1, 10 from dual union
select  3,100 from dual union
select  5,  1 from dual union
select 10,  2 from dual union
select 11,  3 from dual union
select 14, 10 from dual union
select 16, 10 from dual union
select 17,  5 from dual union
select 20,  6 from dual;

SQL

--■■■再帰with句を使う方法(11gR2以降)■■■
with tmp as(
select sortKey,Val,Row_Number() over(order by sortKey) as rn
  from knapSackTable),
rec(rootSortKey,sortKey,rn,sumVal,maxDiff) as(
select sortKey,sortKey,rn,Val,0
  from tmp
 where Val < 9
union all
select a.rootSortKey,b.sortKey,b.rn,
a.sumVal+b.Val,greatest(a.maxDiff,b.sortKey-a.sortKey)
  from rec a,tmp b
 where a.rn+1=b.rn
   and a.sumVal+b.Val < 9)
select rootSortKey,sortKey,sumVal,maxDiff
from (select rootSortKey,sortKey,sumVal,maxDiff,
      max(sumVal) over() as maxSumVal
        from rec)
where sumVal = maxSumVal
order by rootSortKey;

--■■■表関数を使う方法■■■
create or replace Package Pack10_336 Is
    type PrintType is record(
    rootSortKey knapSackTable.sortKey%type,
    sortKey     knapSackTable.sortKey%type,
    sumVal      number(2),
    maxDiff     number(2));

    type PrintTypeSet is table of PrintType;
end;
/

create or replace function PrintR10336 return Pack10_336.PrintTypeSet PipeLined IS
    outR Pack10_336.PrintType;
    cursor cur is select sortKey,Val,Row_Number() over(order by sortKey) as rn from knapSackTable;
    type saveDataDef is table of cur%rowType index by binary_integer;
    saveData saveDataDef;

    type InfoDef is record(
        RowData     cur%rowType,
        rootSortKey knapSackTable.sortKey%type,
        sumVal      number(2),
        maxDiff     number(2)
    );

    stackP binary_integer := 0;
    type StackClass is table of InfoDef index by binary_integer;
    st StackClass;
    priInfo  InfoDef;
    willPush InfoDef;
    IsLeaf boolean;

    procedure push(pInfoDef InfoDef) is
    begin
        st(stackP) := pInfoDef;
        stackP := stackP+1;
    end;

    function pop return InfoDef is
    begin
        stackP := stackP-1;
        return st(stackP);
    end;

    function IsEmpty return boolean is
    begin
        return stackP = 0;
    end;
begin
    open cur;
    fetch cur bulk collect into saveData;
    close cur;

    --Start With句
    for I in 1..saveData.Count Loop
        if saveData(I).Val < 9 then
            willPush.RowData.sortKey := saveData(I).sortKey;
            willPush.RowData.Val     := saveData(I).Val;
            willPush.RowData.rn      := saveData(I).rn;
            willPush.rootSortKey     := saveData(I).sortKey;
            willPush.sumVal          := saveData(I).Val;
            willPush.maxDiff         := 0;

            push(willPush);
        end if;
    end Loop;

    while (IsEmpty = false) loop
        priInfo := pop();
        IsLeaf := true;

        -- connect by句
        for I in 1..saveData.Count Loop
            if priInfo.RowData.rn+1 = saveData(I).rn then
                if priInfo.sumVal + saveData(I).Val < 9 then
                    willPush.RowData.sortKey := saveData(I).sortKey;
                    willPush.RowData.Val     := saveData(I).Val;
                    willPush.RowData.rn      := saveData(I).rn;
                    willPush.rootSortKey     := priInfo.rootSortKey;
                    willPush.sumVal          := priInfo.sumVal+saveData(I).Val;
                    willPush.maxDiff         := greatest(priInfo.maxDiff,
                                                         saveData(I).sortKey
                                                       - priInfo.RowData.sortKey);

                    push(willPush);
                    IsLeaf := false;
                end if;
            end if;
        end Loop;

        --葉なら出力
        if IsLeaf then
            outR.rootSortKey := priInfo.rootSortKey;
            outR.sortKey     := priInfo.RowData.sortKey;
            outR.sumVal      := priInfo.sumVal;
            outR.maxDiff     := priInfo.maxDiff;
            pipe row(outR);
        end if;
    end Loop;
end;
/

sho err

select rootSortKey,sortKey,sumVal,maxDiff
from (select rootSortKey,sortKey,sumVal,maxDiff,
      max(sumVal) over() as maxSumVal
      from table(PrintR10336))
where sumVal = maxSumVal;

解説

再帰with句は、ナップサック問題に強いようですね :-)