手机版
你好,游客 登录 注册 搜索
背景:
阅读新闻

[经典算法]海盗分金问题sql求解(贪心算法)

[日期:2018-09-19] 来源:cnblogs.com/yongestcat  作者:九命猫幺 [字体: ]

问题:

经济学上有个“海盗分金”模型:是说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;

Linux公社的RSS地址:https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2018-09/154203.htm

linux
相关资讯       贪心算法  海盗分金问题  海盗分金 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款