• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1014 – Dividing

    ACM-POJ EXP 222阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    有分别价值为1,2,3,4,5,6的6种物品,输入6个数字,表示相应价值的物品的数量,问一下能不能将物品分成两份,是两份的总价值相等,其中一个物品不能切开,只能分给其中的某一方,当输入六个0是(即没有物品了),这程序结束,总物品的总个数不超过20000

    输出:每个测试用例占三行:

      第一行: Collection #k: k为第几组测试用例

      第二行:是否能分(具体形式见用例)

      第三行:空白(必须注意,否则PE)

    解题思路

    有两种解决方法

    第一种是几乎百度上所有同学都热衷的多重背包,确实这题就是《背包九讲》里面的“多重背包”的应用题,直接套O(V*Σlog n[i])的模板就毫无悬念地AC了,《背包九讲》里面提供的是“多重背包+二进制优化”算法,百度上也有不少同学加入了自己的想法去进一步优化,例如利用“抽屉原理”证明并“取模优化”的可行性等,这些同学都做了不少功课,值得我们学习。

    第二种方法是几乎没有同学使用的DFS,本题用DFS也能0ms跑完,可能大家都被《背包九讲》冲昏了头脑,都想着套模板去了,但又看不懂模板。呻吟“研究了背包多长时间都不完全明白”的同学不妨试试DFS。其实本来不少DP题都可以用搜索过的,大家不要钻牛角尖。

    方法一:多重背包+二进制优化

    转载请注明:EXP 技术分享博客 » POJ1014 – Dividing

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址