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

    ACM-POJ EXP 133阅读 0评论

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


    大致题意

    公司现在要发明一种新的碎纸机,要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值。比如,target的值是50,而纸条上的数字是12346,应该把数字切成四部分,分别是1、2、34、6。因为这样所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。(比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50,而12, 34, 6也不可以,因为它们的和超过50了。碎纸还有以下三个要求:

    1、如果target的值等于纸条上的值,则不能切。

    2、如果没有办法把纸条上的数字切成小于target,则输出error。如target是1而纸条上的数字是123,则无论你如何切得到的和都比1大。

    3、如果有超过一种以上的切法得到最佳值,则输出rejected。如target为15,纸条上的数字是111,则有以下两种切法11、1或者1、11.
    你的任务是编写程序对数字进行划分以达到最佳值。

    解题思路

    DFS深搜

    (1) 比如一个6位数n,切成为6个数的话,这6个数的和如果大于目标数aim则不用再搜索了,因为这肯定是所有划分中和最小的,而最小都比目标数大,自然就没有合要求的答案了.

    (2) 如何切分,假如以50 12346 为例。
      第一步,先切下一个“1”,然后递归去切“2346”;
      第二步,再切下一个“12”,然后递归去切“346”;
      第三步,再切下一个“123”,然后递归去切“46”;
      第四步,再切下一个“1234” 然后递归去切“6”
      第五步,再切下“12346”。

    (3) 切下来的 前面的数字串部分 则加入到划分的和,剩下的部分继续递归,直到剩下的数字串长度为0。 可以用一个int记录划分方式(int p), 如上例的输入为50 12346时,其结果为43 1 2 34 6,那么p=1121,代表把12346划分为4部分,第一部分为第1位,第二部分为第2位,第三部分为第3、4位,第四部分为第5位

    (4) 注意在搜索时,必须把n的 剩余数字部分 转化为字符串再搜索,不然若 剩余的数字开头第一位为 0 时,会导致出错。

    (5) 剪枝方法:在搜索时若发现部分和 大于(不能等于)aim时,则可结束搜索。

    (6) error的判定要在搜索前进行,rejected(多个最优解)的判定要在搜索后判定。

    (7) 关于出现相同最优解的标记,每出每种划分的sum每出现一次标记+1,要使标记为O(1),只需把vist数组开得足够大。N最多为6位数,因此Maxsum=999999


    简单的附上一个关于例50 12346的不完全搜索树

    省略号为未列出的结点

    转载请注明:EXP 技术分享博客 » POJ1416 – Shredding Company

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

    表情

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

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