作者fatcat8127 (胖胖猫)
看板Prob_Solve
标题[问题] ZJ-b952 背包问题(?)
时间Thu Apr 25 00:32:09 2019
如题，题目是一系列的从简单的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。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.136.219
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1556123531.A.9FF.html
1F：推 boqCAE: 应该类似 UVa 562 - Dividing coins 04/27 22:09
2F：推 boqCAE: 哦.. 我上面贴的就是对应分堆问题(b951) 04/27 22:21
3F：→ boqCAE: 大魔王则是数字大到 TLE 04/27 22:21
4F：→ fatcat8127: 我试过用set 维护过程中出现的数字，但1e4会产生的数 04/29 02:08
5F：→ fatcat8127: 量过多，基本上是直接吃SE的(即使可以也会吃TLE) 04/29 02:09
※ 编辑: fatcat8127 (61.222.86.91 台湾), 06/22/2019 23:25:14