海盗分金c语言算法 [经典算法]海盗分金问题sql求解（贪心算法）

问题：

经济学上有个“海盗分金”模型：是说5个海盗抢得100枚金币，他们按抽签的顺序依次提方案：首先由1号提出分配方案，然后5人表决，超过半数同意方案才被通过，否则他将被扔入大海喂鲨鱼，依此类推,假设海盗是足够聪明的先利己再伤人，最后方案是怎样的？

网上百度来的的代码：

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;

严格筛选数据，优化后

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;