‹ 上一题 下一题 ›

g6-07173. 剪枝·追平不算追不上 未做

1000 ms 256 MB 测试点 ? 自拟题知识点题GESP-66级·深度优先搜索客观题单选

个宝箱排成一排,每个宝箱价值都是正整数,逐个决定拿或不拿,求能拿到的最大总价值。已搜出一条纪录:最优值 。现在搜到第 个宝箱,已得 分,剩下所有宝箱全部拿满最多再加 分。此刻能否直接放弃这条分支?正确的判断是( )。

  • A. 不能剪: 正好追平纪录,这条分支里可能还藏着并列最优的方案,只有「严格追不上」才放心剪
  • B. 能剪:当前得分 已经小于纪录 ,眼前落后就没有希望了
  • C. 能剪:追平也算没戏,「不超过纪录」的分支统统该放弃
  • D. 不能剪,但理由是:不管追不追得上,搜索都必须把每一种方案走完才严谨
未选择
输入
输出

            
答案