トップページに戻る
次のPL/SQLの問題へ
前のPL/SQLの問題へ
Java版
PL/SQL2 ナップサック問題
SQLパズル
ALGORITHM NOTE ナップザック問題 Knapsack Problem
5つの荷物（重量と価値はそれぞれ、（3と4）（4と5）（5と6）（6と7）（9と10） が各1個）がある。
重量の合計が15以内で、最も価値の合計が高くなるような荷物の組合せを見つけよ。
荷物名 重量 価値
------ ---- ----
A 3 4
B 4 5
C 5 6
D 6 7
E 9 10
データ作成スクリプト
create table nimotuT(nimotu,KG,Val) as
select 'a',3, 4 from dual union
select 'b',4, 5 from dual union
select 'c',5, 6 from dual union
select 'd',6, 7 from dual union
select 'e',9,10 from dual;
SQL(全ての組み合わせを列挙)
col nimotuList for a20
select a.nimotuList,sum(b.KG) as sumKG,sum(b.Val) as sumVal
from (select KG,Val,sys_connect_by_path(nimotu,',') as nimotuList,
sys_connect_by_path(RowIDToChar(RowID),',') as RowIDList
from (select KG,Val,nimotu,Row_Number() over(order by KG) as rn
from nimotuT)
connect by prior rn+1 = rn) a,
nimotuT b
where instr(a.RowIDList,RowIDToChar(b.RowID)) > 0
group by a.nimotuList
having sum(b.KG) <=15
order by sumVal desc,sumKG desc,a.nimotuList;
nimotuList sumKG sumVal
---------- ----- ------
,b,c,d 15 18
,d,e 15 17
,a,b,c 12 15
,c,d 11 13
,b,c 9 11
,e 9 10
,a,b 7 9
,d 6 7
,c 5 6
,b 4 5
,a 3 4
PL/SQL(全ての組み合わせを列挙)
declare
sumKG pls_Integer;
sumVal pls_Integer;
willOut Varchar2(100);
begin
for A in 0..1 Loop
for B in 0..1 Loop
for C in 0..1 Loop
for D in 0..1 Loop
for E in 0..1 Loop
sumKG := 0; sumVal :=0;
if A=1 then sumKG:= sumKG+3; sumVal:= sumVal+ 4; end if;
if B=1 then sumKG:= sumKG+4; sumVal:= sumVal+ 5; end if;
if C=1 then sumKG:= sumKG+5; sumVal:= sumVal+ 6; end if;
if D=1 then sumKG:= sumKG+6; sumVal:= sumVal+ 7; end if;
if E=1 then sumKG:= sumKG+9; sumVal:= sumVal+10; end if;
willOut := null;
if sumKG <= 15 and 0 < sumVal then
if A = 1 then willOut := willOut || 'A'; end if;
if B = 1 then willOut := willOut || 'B'; end if;
if C = 1 then willOut := willOut || 'C'; end if;
if D = 1 then willOut := willOut || 'D'; end if;
if E = 1 then willOut := willOut || 'E'; end if;
willOut := willOut || ',sumKG=' || to_char(sumKG);
willOut := willOut || ',sumVal=' || to_char(sumVal);
DBMS_Output.Put_Line(willOut);
end if;
end Loop;
end Loop;
end Loop;
end Loop;
end Loop;
end;
/
PL/SQL(動的計画法)
declare
cursor cur is select nimotu,KG,Val from nimotuT order by nimotu;
type SaveDataDef is table of cur%rowType index by binary_integer;
SaveData SaveDataDef;
--重さ合計の制限
OmosaSumLimit Constant pls_Integer :=15;
--添字が重さの合計、値が価値合計の最大値
type SumValArrDef is table of pls_Integer index by binary_integer;
SumValArr SumValArrDef;
--最後に矢印をセットした品物の名称
type LastArrowItemArrDef is table of char(1) index by binary_integer;
LastArrowItemArr LastArrowItemArrDef;
type LastArrowItemArrLogDef is table of LastArrowItemArrDef index by binary_integer;
LastArrowItemArrLog LastArrowItemArrLogDef;
wkSumOmosa pls_Integer;
wkSumVal pls_Integer;
CanUpdate Boolean;
--動的計画法の現在の状態を表示
procedure PrintJyoutai is
WillOut1 VarChar2(4000);
WillOut2 VarChar2(4000);
WillOut3 VarChar2(4000);
begin
for I in 0..OmosaSumLimit Loop
WillOut1 := WillOut1 || '[' || LPad(to_char(I),2) || ']';
WillOut2 := WillOut2 || case when SumValArr.Exists(I)
then '[' || LPad(to_char(SumValArr(I)),2) || ']'
else '[ ]' end;
WillOut3 := WillOut3 || case when LastArrowItemArr.Exists(I)
then '[' || LPad(to_char(LastArrowItemArr(I)),2) || ']'
else '[ ]' end;
end Loop;
DBMS_Output.Put_Line(WillOut1);
DBMS_Output.Put_Line(WillOut2);
DBMS_Output.Put_Line(WillOut3);
end;
--動的計画法の結果を表示
procedure PrintResult is
MaxSumVal pls_Integer := 0;
MaxSumInd binary_integer := 0;
CurrInd binary_integer := 0;
CurrLog LastArrowItemArrDef;
type SelectedItemListDef is table of char(1) index by binary_integer;
SelectedItemList SelectedItemListDef;
WillOut VarChar2(4000);
begin
--最大の価値を持つ、重さ合計を求める
for I in 0..OmosaSumLimit Loop
if SumValArr.Exists(I) then
if MaxSumVal < SumValArr(I) then
MaxSumVal := SumValArr(I);
MaxSumInd := I;
end if;
end if;
end Loop;
DBMS_Output.Put_Line('重さ合計が' || to_char(OmosaSumLimit) || '以下での最大の価値は、');
DBMS_Output.Put_Line('重さ合計=' || to_char(MaxSumInd)
|| 'で価値合計=' || to_char(MaxSumVal) || 'です。');
DBMS_Output.Put_Line('■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■');
DBMS_Output.Put_Line('選択した荷物を表示します。');
CurrInd := MaxSumInd;
for I in Reverse 0..LastArrowItemArrLog.Count-1 Loop
CurrLog := LastArrowItemArrLog(I);
--使用済の荷物を含むログならContinue
for J in 0..CurrLog.Count-1 Loop
for K in 0..SelectedItemList.Count-1 Loop
if CurrLog.Exists(J) and CurrLog(J) = SelectedItemList(K) then
goto Continue001;
end if;
end Loop;
end Loop;
for J in 1..SaveData.Count Loop
if SaveData(J).nimotu = CurrLog(CurrInd) then
WillOut := 'ID=' || SaveData(J).nimotu || '、';
WillOut := WillOut || '重さ= ' || SaveData(J).KG || '、';
WillOut := WillOut || '価値= ' || SaveData(J).Val;
DBMS_Output.Put_Line(WillOut);
SelectedItemList(SelectedItemList.Count) := SaveData(J).nimotu;
CurrInd := CurrInd - SaveData(J).KG;
exit;
end if;
end Loop;
exit when CurrInd = 0;
<<Continue001>> null;
end Loop;
end;
begin
open cur;
fetch cur bulk collect into SaveData;
close cur;
--初期設定
SumValArr(0) := 0;
for I in 1..SaveData.Count Loop
for J in Reverse 0..OmosaSumLimit Loop
--重さ制限を超えてしまう場合
wkSumOmosa := J+SaveData(I).KG;
if wkSumOmosa > OmosaSumLimit then goto Continue002; end if;
--価値の和を求める
if SumValArr.Exists(J) = false then goto Continue002; end if;
wkSumVal := SumValArr(J) + SaveData(I).Val;
--重さ合計での最大の価値を更新可能かを判定
CanUpdate := false;
if SumValArr.Exists(wkSumOmosa) = false then
CanUpdate := true;
elsif SumValArr(wkSumOmosa) < wkSumVal then
CanUpdate := true;
end if;
if CanUpdate then
SumValArr(wkSumOmosa) := wkSumVal;
LastArrowItemArr(wkSumOmosa) := SaveData(I).nimotu;
end if;
<<Continue002>> null;
end Loop;
LastArrowItemArrLog(LastArrowItemArrLog.Count) := LastArrowItemArr;
DBMS_Output.Put_Line('■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■');
DBMS_Output.Put_Line(SaveData(I).nimotu || 'の処理結果');
PrintJyoutai();
end Loop;
DBMS_Output.Put_Line('■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■');
DBMS_Output.Put_Line('動的計画法の結果を表示します。');
PrintResult();
end;
/
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
aの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12][13][14][15]
[ 0][ ][ ][ 4][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ a][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
bの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12][13][14][15]
[ 0][ ][ ][ 4][ 5][ ][ ][ 9][ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ a][ b][ ][ ][ b][ ][ ][ ][ ][ ][ ][ ][ ]
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
cの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12][13][14][15]
[ 0][ ][ ][ 4][ 5][ 6][ ][ 9][10][11][ ][ ][15][ ][ ][ ]
[ ][ ][ ][ a][ b][ c][ ][ b][ c][ c][ ][ ][ c][ ][ ][ ]
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
dの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12][13][14][15]
[ 0][ ][ ][ 4][ 5][ 6][ 7][ 9][10][11][12][13][15][16][17][18]
[ ][ ][ ][ a][ b][ c][ d][ b][ c][ c][ d][ d][ c][ d][ d][ d]
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
eの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12][13][14][15]
[ 0][ ][ ][ 4][ 5][ 6][ 7][ 9][10][11][12][13][15][16][17][18]
[ ][ ][ ][ a][ b][ c][ d][ b][ c][ c][ d][ d][ c][ d][ d][ d]
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
動的計画法の結果を表示します。
重さ合計が15以下での最大の価値は、
重さ合計=15で価値合計=18です。
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
選択した荷物を表示します。
ID=d、重さ= 6、価値= 7
ID=c、重さ= 5、価値= 6
ID=b、重さ= 4、価値= 5
解説
全ての組み合わせを列挙するよりも、動的計画法で解いたほうが、計算量は、少ないです。