[問題] DFS剪枝

[fatcat8127 (胖胖貓)]

一開始看到想到的解法是改編於 uva10364 的題目。

(1) 將所有的線段加總後的總長度做質因數分解，只保留因數的數值大於等於最大線段長

    的數值 這些因數都可能是筷子的長度。

(2) 將輸入的線段由大到小排列，因數部分由小到大排列。 枚舉所有可能的因數直到成功

    成功的定義為可以用所有的線段組出剛好邊長。

    但是 d375-uva10364 的題目測資範圍只有20個片段組成，

    這題最多會到達50個， 如果挑戰失敗意謂著會把所有可能嘗試過都無法組出來，

    所以需要更好的剪枝來達成。

b597: Stickst(https://zerojudge.tw/ShowProblem?problemid=b597)

這是我寫的Code:https://www.codepile.net/pile/n1V8MnyY

不過會吃TLE，想問說還有哪部分可以剪枝但沒注意到。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.208.164
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1552551296.A.117.html
推 rareone: 1. 嘗試從最長開始排到最短的話呢，可以 greedy 如果有 [
→ rareone: 2, 3] 跟 [5] 的 sticks 可用，永遠先考慮拿 [5]
→ rareone: 2. 可以 DP 記住 [目前的根數] [iter 到哪一根] [目前這
→ rareone: 一根iter 多長]
推 rareone: 唔 我2. 好像有細節上的 bug 再想想
推 rareone: 2. 用 bitmask 雙向進行 BFS，狀態存 set，每次排出來看
→ rareone: 一下他的 complement是不是在另一頭BFS走過了
→ rareone: BTW 檢定性質的 bi-BFS 有隨機性的算法，就是兩端隨便生
→ rareone: m 條 k/2-path 然後
→ rareone: meet-in-the-middle 比對
推 CathyP: 先排序然後從最小的因數開始測,去掉不可能的情形
→ CathyP: 1. 除出來的組數超過陣列大小 2. 陣列最大值大於因數
→ CathyP: 進行DFS時1.跳過重複的起點2.false的情形如果目前和為零
→ CathyP: 表示不可能完成分組,直接early return
→ CathyP: 3.每組的起點都由陣列中未使用的最大值開始
→ fatcat8127: 可以理解因數必須大於等於從片段中最長邊長
→ fatcat8127: 但DFS的實作不是很清楚
推 CathyP: 比方說A = [1,1,1,1,2,3],最初的DFS從sum = 0, pos = 0跑
→ CathyP: 這層的DFS會以for (int i = pos;)開始測A[i] + sum
→ CathyP: 同一層DFS上一個拿來測的叫A[j]好了, 當A[i] == A[j]跳過
→ CathyP: 意思是說同一個位置不需要測試相同長度的A[i]
→ CathyP: 另外假設該層DFS sum = 0,但找不到解,就表示沒有任何組合
→ CathyP: 可以滿足條件,就可以early return
→ fatcat8127: 感謝大大 雖然不吃TLE 不過還是WA 不知道哪邊掛掉
→ fatcat8127: 第五組我會輸出83不過答案是1411，第七組是36答案是48
→ fatcat8127: 附上code: https://www.codepile.net/pile/6KLP3mKo
→ fatcat8127: 剛剛發現dfs寫錯，調整後還是tle QQ
推 CathyP: 質因數分解那一段不需要做, 直接從1開始測試
→ CathyP: use array不需要每次都memset,一開始做一次就好
→ CathyP: 因為當A[i]不能拿來用,應該把use[i]還原
推 CathyP: DFS中的start應該由陣列尾端開始(Greedy)
→ CathyP: 完成一個Group後,由陣列尾端往前找尚未使用的
→ CathyP: 當下一層DFS的起點
→ CathyP: nowLen=0時,DFS又回傳false就要early return了
→ CathyP: 不需要繼續iterate下去因為這表示該A[i]找不到任何解
→ CathyP: 變數應該避免使用global variable, 容易錯
→ fatcat8127: 質因數分解的目的不是必須的嗎?這樣才能保證找到可以
→ fatcat8127: 整除邊長的邊數和剪枝。for迴圈外面有個return false
→ fatcat8127:  就是當現在不存一條邊滿足時就回傳false
→ fatcat8127: 附上修改後的程式碼: https://www.codepile.net/pile
→ fatcat8127: /WKrglxeG
推 cutekid: 第 39 行 use[i] = 0; 下面增加一句
→ cutekid: if(nowLen == 0) break;
→ fatcat8127: 感謝 cutekid 和 CathyP 兩位大大耐心的指導和協助。
→ fatcat8127: 感謝第一位回覆我的rareone大大，但我不太會雙向BFS
→ fatcat8127: 和記憶化搜索方式，大概知道你說的方式
→ fatcat8127: 附上實作：https://www.codepile.net/pile/ZOggAkOQ
→ fatcat8127: 阿 2ms版本應該是測資較弱沒測出來，測資 : 15 34 38
→ fatcat8127:  10 44 45 7 13 30 44 43 47 43 27 38 5
→ fatcat8127: 答案是117
推 FRAXIS: 當你在測試 edgeLen 可不可行的時候
→ FRAXIS: 可以用 DP 嗎？ 先找找有沒有一個 subset sum = edgeLen
→ FRAXIS: 有的話 就拿掉那個 subset 然後 repeat 直到所有元素都
→ FRAXIS: 用完為止， subset sum 用 DP 應該很容易作
→ fatcat8127: 應該無法，同樣是我舉例的測資，如果先移除(43,44,30
→ fatcat8127: )和(47,45,5,7,13)剩餘的片段無法構成兩個117
推 CathyP: 你的測資答案是161才對喔, 總和是483
→ CathyP: 質因數分解不是必須 https://onlinegdb.com/S1e-oK7_V
→ fatcat8127: 第一個15是輸入15個數字的意思
→ fatcat8127: 第40行程式碼是線性偵查目前的線段長度是不是總長度
→ fatcat8127: 的因數，因為測資的總長度不超過2500所以無論是線性
→ fatcat8127: 或是先做質因數分解找因數，時間差異不大。
推 FRAXIS: 那如果用 DP 先找出所有的 subset sum 然後再 DFS ？
→ FRAXIS: 只是這樣做起來比較麻煩就是了
推 FRAXIS: 從你原本的程式看起來 把 unused set 用 BST 存起來
→ FRAXIS: 會不會比較方便找解答？
推 CathyP: 你的沒跑出117是出在line 39那邊沒檢查回傳值所以錯誤
→ fatcat8127: 感謝C大 那邊如果判斷失誤應該要還原use[i]的狀態
→ fatcat8127: 根據FRAXIS大大的想應該是找出所有可以構成現在邊長
→ fatcat8127: 用到的所有狀態集合，從這堆集合中找出一組存在每個
→ fatcat8127: 片段只會用一次，這個問題等價於ZJ-a207需要用dancin
→ fatcat8127: g link 解且存在狀態過多的風險。 我先理解一下a207
→ fatcat8127: 的題目....