PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] DFS剪枝

看板Prob_Solve (計算數學 Problem Solving)作者 (胖胖貓)時間5年前 (2019/03/14 16:14), 編輯推噓13(13推 0噓 60→)
留言73則, 5人參與, 5年前最新討論串1/1
一開始看到想到的解法是改編於 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
推
03/19 20:01, 5年前 , 1F
1. 嘗試從最長開始排到最短的話呢，可以 greedy 如果有 [
03/19 20:01, 1F
→
03/19 20:01, 5年前 , 2F
2, 3] 跟 [5] 的 sticks 可用，永遠先考慮拿 [5]
03/19 20:01, 2F
→
03/19 20:02, 5年前 , 3F
2. 可以 DP 記住 [目前的根數] [iter 到哪一根] [目前這
03/19 20:02, 3F
→
03/19 20:02, 5年前 , 4F
一根iter 多長]
03/19 20:02, 4F
推
03/19 20:04, 5年前 , 5F
唔 我2. 好像有細節上的 bug 再想想
03/19 20:04, 5F
推
03/19 20:17, 5年前 , 6F
2. 用 bitmask 雙向進行 BFS，狀態存 set，每次排出來看
03/19 20:17, 6F
→
03/19 20:17, 5年前 , 7F
一下他的 complement是不是在另一頭BFS走過了
03/19 20:17, 7F
→
03/19 20:20, 5年前 , 8F
BTW 檢定性質的 bi-BFS 有隨機性的算法，就是兩端隨便生
03/19 20:20, 8F
→
03/19 20:20, 5年前 , 9F
m 條 k/2-path 然後
03/19 20:20, 9F
→
03/19 20:21, 5年前 , 10F
meet-in-the-middle 比對
03/19 20:21, 10F
推
03/20 23:01, 5年前 , 11F
先排序然後從最小的因數開始測,去掉不可能的情形
03/20 23:01, 11F
→
03/20 23:02, 5年前 , 12F
1. 除出來的組數超過陣列大小 2. 陣列最大值大於因數
03/20 23:02, 12F
→
03/20 23:04, 5年前 , 13F
進行DFS時1.跳過重複的起點2.false的情形如果目前和為零
03/20 23:04, 13F
→
03/20 23:04, 5年前 , 14F
表示不可能完成分組,直接early return
03/20 23:04, 14F
→
03/20 23:05, 5年前 , 15F
3.每組的起點都由陣列中未使用的最大值開始
03/20 23:05, 15F
→
03/21 00:27, 5年前 , 16F
可以理解因數必須大於等於從片段中最長邊長
03/21 00:27, 16F
→
03/21 00:28, 5年前 , 17F
但DFS的實作不是很清楚
03/21 00:28, 17F
推
03/21 09:39, 5年前 , 18F
比方說A = [1,1,1,1,2,3],最初的DFS從sum = 0, pos = 0跑
03/21 09:39, 18F
→
03/21 09:41, 5年前 , 19F
這層的DFS會以for (int i = pos;)開始測A[i] + sum
03/21 09:41, 19F
→
03/21 09:42, 5年前 , 20F
同一層DFS上一個拿來測的叫A[j]好了, 當A[i] == A[j]跳過
03/21 09:42, 20F
→
03/21 09:43, 5年前 , 21F
意思是說同一個位置不需要測試相同長度的A[i]
03/21 09:43, 21F
→
03/21 09:46, 5年前 , 22F
另外假設該層DFS sum = 0,但找不到解,就表示沒有任何組合
03/21 09:46, 22F
→
03/21 09:46, 5年前 , 23F
可以滿足條件,就可以early return
03/21 09:46, 23F
→
03/21 15:21, 5年前 , 24F
感謝大大 雖然不吃TLE 不過還是WA 不知道哪邊掛掉
03/21 15:21, 24F
→
03/21 15:22, 5年前 , 25F
第五組我會輸出83不過答案是1411，第七組是36答案是48
03/21 15:22, 25F
→
03/21 15:24, 5年前 , 26F
03/21 15:24, 26F
→
03/21 15:59, 5年前 , 27F
剛剛發現dfs寫錯，調整後還是tle QQ
03/21 15:59, 27F
推
03/21 17:36, 5年前 , 28F
質因數分解那一段不需要做, 直接從1開始測試
03/21 17:36, 28F
→
03/21 17:38, 5年前 , 29F
use array不需要每次都memset,一開始做一次就好
03/21 17:38, 29F
→
03/21 17:39, 5年前 , 30F
因為當A[i]不能拿來用,應該把use[i]還原
03/21 17:39, 30F
推
03/21 17:44, 5年前 , 31F
DFS中的start應該由陣列尾端開始(Greedy)
03/21 17:44, 31F
→
03/21 17:45, 5年前 , 32F
完成一個Group後,由陣列尾端往前找尚未使用的
03/21 17:45, 32F
→
03/21 17:45, 5年前 , 33F
當下一層DFS的起點
03/21 17:45, 33F
→
03/21 17:47, 5年前 , 34F
nowLen=0時,DFS又回傳false就要early return了
03/21 17:47, 34F
→
03/21 17:48, 5年前 , 35F
不需要繼續iterate下去因為這表示該A[i]找不到任何解
03/21 17:48, 35F
→
03/21 17:50, 5年前 , 36F
變數應該避免使用global variable, 容易錯
03/21 17:50, 36F
→
03/22 13:49, 5年前 , 37F
質因數分解的目的不是必須的嗎?這樣才能保證找到可以
03/22 13:49, 37F
→
03/22 13:49, 5年前 , 38F
整除邊長的邊數和剪枝。for迴圈外面有個return false
03/22 13:49, 38F
→
03/22 13:49, 5年前 , 39F
就是當現在不存一條邊滿足時就回傳false
03/22 13:49, 39F
→
03/22 13:52, 5年前 , 40F
附上修改後的程式碼: https://www.codepile.net/pile
03/22 13:52, 40F
→
03/22 13:52, 5年前 , 41F
/WKrglxeG
03/22 13:52, 41F
推
03/22 14:41, 5年前 , 42F
第 39 行 use[i] = 0; 下面增加一句
03/22 14:41, 42F
→
03/22 14:41, 5年前 , 43F
if(nowLen == 0) break;
03/22 14:41, 43F
→
03/22 15:05, 5年前 , 44F
感謝 cutekid 和 CathyP 兩位大大耐心的指導和協助。
03/22 15:05, 44F
→
03/22 15:12, 5年前 , 45F
感謝第一位回覆我的rareone大大，但我不太會雙向BFS
03/22 15:12, 45F
→
03/22 15:12, 5年前 , 46F
和記憶化搜索方式，大概知道你說的方式
03/22 15:12, 46F
→
03/22 16:02, 5年前 , 47F
03/22 16:02, 47F
→
03/22 18:20, 5年前 , 48F
阿 2ms版本應該是測資較弱沒測出來，測資 : 15 34 38
03/22 18:20, 48F
→
03/22 18:20, 5年前 , 49F
10 44 45 7 13 30 44 43 47 43 27 38 5
03/22 18:20, 49F
→
03/22 18:20, 5年前 , 50F
答案是117
03/22 18:20, 50F
推
03/23 11:13, 5年前 , 51F
當你在測試 edgeLen 可不可行的時候
03/23 11:13, 51F
→
03/23 11:14, 5年前 , 52F
可以用 DP 嗎？ 先找找有沒有一個 subset sum = edgeLen
03/23 11:14, 52F
→
03/23 11:14, 5年前 , 53F
有的話 就拿掉那個 subset 然後 repeat 直到所有元素都
03/23 11:14, 53F
→
03/23 11:14, 5年前 , 54F
用完為止， subset sum 用 DP 應該很容易作
03/23 11:14, 54F
→
03/23 16:26, 5年前 , 55F
應該無法，同樣是我舉例的測資，如果先移除(43,44,30
03/23 16:26, 55F
→
03/23 16:26, 5年前 , 56F
)和(47,45,5,7,13)剩餘的片段無法構成兩個117
03/23 16:26, 56F
推
03/23 18:32, 5年前 , 57F
你的測資答案是161才對喔, 總和是483
03/23 18:32, 57F
→
03/23 18:33, 5年前 , 58F
質因數分解不是必須 https://onlinegdb.com/S1e-oK7_V
03/23 18:33, 58F
→
03/23 23:57, 5年前 , 59F
第一個15是輸入15個數字的意思
03/23 23:57, 59F
→
03/24 00:21, 5年前 , 60F
第40行程式碼是線性偵查目前的線段長度是不是總長度
03/24 00:21, 60F
→
03/24 00:21, 5年前 , 61F
的因數，因為測資的總長度不超過2500所以無論是線性
03/24 00:21, 61F
→
03/24 00:21, 5年前 , 62F
或是先做質因數分解找因數，時間差異不大。
03/24 00:21, 62F
推
03/24 06:15, 5年前 , 63F
那如果用 DP 先找出所有的 subset sum 然後再 DFS ？
03/24 06:15, 63F
→
03/24 06:15, 5年前 , 64F
只是這樣做起來比較麻煩就是了
03/24 06:15, 64F
推
03/24 06:27, 5年前 , 65F
從你原本的程式看起來 把 unused set 用 BST 存起來
03/24 06:27, 65F
→
03/24 06:27, 5年前 , 66F
會不會比較方便找解答？
03/24 06:27, 66F
推
03/24 21:43, 5年前 , 67F
你的沒跑出117是出在line 39那邊沒檢查回傳值所以錯誤
03/24 21:43, 67F
→
03/25 07:55, 5年前 , 68F
感謝C大 那邊如果判斷失誤應該要還原use[i]的狀態
03/25 07:55, 68F
→
03/28 13:28, 5年前 , 69F
根據FRAXIS大大的想應該是找出所有可以構成現在邊長
03/28 13:28, 69F
→
03/28 13:28, 5年前 , 70F
用到的所有狀態集合，從這堆集合中找出一組存在每個
03/28 13:28, 70F
→
03/28 13:28, 5年前 , 71F
片段只會用一次，這個問題等價於ZJ-a207需要用dancin
03/28 13:28, 71F
→
03/28 13:28, 5年前 , 72F
g link 解且存在狀態過多的風險。 我先理解一下a207
03/28 13:28, 72F
→
03/28 13:28, 5年前 , 73F
的題目....
03/28 13:28, 73F
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1SYWs04N (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1SYWs04N (Prob_Solve)