海盜分金問題SQL求解(貪心算法)
問題
經(jīng)濟(jì)學(xué)上有個“海盜分金”模型:是說5個海盜搶得100枚金幣,他們按抽簽的順序依次提方案:首先由1號提出分配方案,然后5人表決,超過半數(shù)同意方案才被通過,否則他將被扔入大海喂鯊魚,依此類推,假設(shè)海盜是足夠聰明的先利己再傷人,最后方案是怎樣的?
網(wǎng)上百度來的的代碼
with a as (select 101 - rownum n from dual connect by rownum <102), max_one as (select max(n) max1 from a), max_two as (select /*+leading(p2,p1) use_nl(p1) */ p2.n max2,p1.n max1 from a p1,a p2 where p1.n+p2.n=100 and p1.n=(select max1 from max_one) and rownum=1), max_three as (select /*+leading(p3,p2,p1) use_nl(p2) use_nl(p1)*/ p3.n max3,p2.n max2,p1.n max1 from a p1,a p2,a p3,max_two where p1.n+p2.n+p3.n=100 and sign(p2.n-max2)+sign(p1.n-max1)>=0 and rownum=1), max_four as (select /*+leading(p4,p3,p2,p1) use_nl(p3) use_nl(p2) use_nl(p1)*/ p4.n max4,p3.n max3,p2.n max2,p1.n max1 from a p1,a p2,a p3,a p4,max_three where p1.n+p2.n+p3.n+p4.n=100 and sign(p3.n-max3)+sign(p2.n-max2)+sign(p1.n-max1)>0 and rownum=1), five as (select /*+leading(p5,p4,p3,p2,p1) use_nl(p4) use_nl(p3) use_nl(p2) use_nl(p1)*/ p5.n n5, p4.n n4,p3.n n3,p2.n n2,p1.n n1 from a p1,a p2,a p3,a p4,a p5,max_four where p1.n+p2.n+p3.n+p4.n+p5.n=100 and sign(p4.n-max4)+sign(p3.n-max3)+sign(p2.n-max2)+sign(p1.n-max1)>=0 and rownum=1) select * from five;
嚴(yán)格篩選數(shù)據(jù)優(yōu)化后
with a as
(select 101 - rownum n from dual connect by rownum <102),
max_one as
(select max(n) max1 from a),
max_two as
(select /*+leading(max_one,p2,p1) use_nl(p2) use_nl(p1) */ p2.n max2,p1.n max1
from a p1,a p2,max_one
where p1.n+p2.n=100
and p1.n>=max1
and rownum=1),
max_three as
(select /*+leading(max_two,p3,p2,p1) use_nl(max_two) use_nl(p2) use_nl(p1)*/ p3.n max3,p2.n max2,p1.n max1
from a p1,a p2,a p3,max_two
where p1.n+p2.n+p3.n=100
AND p3.n+p2.n<=100
and CASE WHEN p2.n > max2 THEN 1 ELSE -1 END +
CASE WHEN p1.n > max1 THEN 1 ELSE -1 END >= 0
and rownum=1),
max_four as
(select /*+leading(max_three,p4,p3,p2,p1) use_nl(max_three) use_nl(p3) use_nl(p2) use_nl(p1)*/ p4.n max4,p3.n max3,p2.n max2,p1.n max1
from a p1,a p2,a p3,a p4,max_three
where p1.n+p2.n+p3.n+p4.n=100
AND p4.n+p3.n <= 100
AND p4.n+p3.n+p2.n <= 100
and CASE WHEN p3.n > max3 THEN 1 ELSE -1 END +
CASE WHEN p2.n > max2 THEN 1 ELSE -1 END +
CASE WHEN p1.n > max1 THEN 1 ELSE -1 END >= 0
and rownum=1),
five as
(select /*+leading(max_four,p5,p4,p3,p2,p1) use_nl(p5) use_nl(p4) use_nl(p3) use_nl(p2) use_nl(p1)*/ p5.n n5, p4.n n4,p3.n n3,p2.n n2,p1.n n1
from a p1,a p2,a p3,a p4,a p5,max_four
where p1.n+p2.n+p3.n+p4.n+p5.n=100
AND p5.n+p4.n <= 100
AND p5.n+p4.n+p3.n <= 100
AND p5.n+p4.n+p3.n+p2.n <= 100
AND CASE WHEN p4.n > max4 THEN 1 ELSE -1 END +
CASE WHEN p3.n > max3 THEN 1 ELSE -1 END +
CASE WHEN p2.n > max2 THEN 1 ELSE -1 END +
CASE WHEN p1.n > max1 THEN 1 ELSE -1 END >= 0
and rownum=1)
select * from five;
結(jié)果

作者:九命貓幺
博客出處:http://www.rzrgm.cn/yongestcat/
歡迎轉(zhuǎn)載,轉(zhuǎn)載請標(biāo)明出處。
如果你覺得本文還不錯,對你的學(xué)習(xí)帶來了些許幫助,請幫忙點(diǎn)擊右下角的推薦
博客出處:http://www.rzrgm.cn/yongestcat/
歡迎轉(zhuǎn)載,轉(zhuǎn)載請標(biāo)明出處。
如果你覺得本文還不錯,對你的學(xué)習(xí)帶來了些許幫助,請幫忙點(diǎn)擊右下角的推薦

浙公網(wǎng)安備 33010602011771號