[问题] ZJ-b952 背包问题(已解决?)

楼主: fatcat8127 (胖胖猫)   2019-04-25 00:32:09
如题,题目是一系列的从简单的DFS(b942: 轰轰岛)
再到经典的01背包问题转换为分堆问题(b951: 轰轰轰轰岛)透过算法的动态规划解题,
最后是大魔王的这题(b952: 轰轰轰轰轰轰岛)。
观察输入的测资可以发现输入的数字虽然只有1e4个,但数字总和可高达2147483647
这样该怎么把分堆问题的概念套用到这题呢?还是说有不同思维的解决方式(?)
完全没有头绪或是关键字可以搜索(可以区隔开背包问题)...
=== 以下是作弊方法并不存在最佳解 ===
背包问题本身就是 NP-hard Problem,不存在多项式时间内的解法。
具体的介绍就请大家到wiki上看看:https://pse.is/GPDME
根据 boqCAE 大大提出的判断方式,先判断 N<=30,否则就将一半的总和视为最佳解。
但这个说法显然是不正确的,比如有9999个31时是会出现问题的...,所以才会是作弊法
只讨论当 N<=30 时是否可以有效解决。
一般采用 DFS 搭配有效的剪枝但会卡在第一笔测资TLE吃到饱。
感谢 vincent97198 的测试:https://ideone.com/GnKv1U
TLE的主要原因是第一笔测资的第一个case(再作弊一次...直接输出答案),
剪枝(内容我写在注解)加上GCC的优化代码,具体优化的原理...
我看了一遍知乎上的讨论还是半懂不懂(https://www.zhihu.com/question/27090458)
我自己采用双向BFS的概念,将30组数字分成两组各自产生 2^15 (32768)个数字。
做二分搜寻配对找到最接近总和一半的组合。
双向 BFS 作法:https://ideone.com/GnKv1U
TLE主因是第二笔测资,我测试后的上限是 N<=42 再多也是吃TLE。
作者: boqCAE (煌)   2019-04-27 22:09:00
应该类似 UVa 562 - Dividing coins哦.. 我上面贴的就是对应分堆问题(b951)大魔王则是数字大到 TLE
楼主: fatcat8127 (胖胖猫)   2019-04-29 02:08:00
我试过用set 维护过程中出现的数字,但1e4会产生的数量过多,基本上是直接吃SE的(即使可以也会吃TLE)

Links booklink

Contact Us: admin [ a t ] ucptt.com