作者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/m.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