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

Re: [問題] 大地排關問題

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間10年前 (2014/03/01 01:52)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串2/5 (看更多)

給出跑不完結果的程式： http://pastie.org/8812754 http://ideone.com/0aZL0G 對戰組合狀態24個，加上(6-8/2)*6=12個休關，總數36 基本上一開始產生狀態就不要考慮會重複。也就是產生不重複的所有狀態再加上休關共36個。程式執行結果： list size is 24 1_8 1_7 1_6 1_5 1_4 1_3 2_8 2_7 2_6 2_5 2_4 2_3 3_8 3_7 3_6 3_5 4_8 4_7 4_6 4_5 5_8 5_7 6_8 6_7 sleep sleep sleep sleep sleep sleep sleep sleep sleep sleep sleep sleep total need 36 6 (cpu i7-3770，5分鐘連6個時段都跑不完) 代碼很簡單，有寫錯或問題可以提出討論。程式可以提供進行修改。 ※ 引述《qaz00123 (00123)》之銘言： : 本身不是資工系但是以前有稍微接觸演算法 : 最近剛好營隊要排對戰表想說自己來寫寫看 : 大概規則是 ( 文字表達能力薄弱orz 文末附上對戰表的大概樣子 ) : n關 m小隊 : 總共有n個時段， : 每小隊都要玩到每一關， : 每個時段中每關要有兩個小隊在同一關 : 同個時段不可以有小隊同時出現在不同的兩關 : 每關會休關 n-m/2 個時段 : 盡量不重複對上之前對過的小隊 : 目前想法是用DFS慢慢找 : 每找到一組可行的解就記錄對上重複小隊的次數 : 然後找最小的。 : 想問問看有沒有更好的方法？ : ( 雖然我還在磨DFS要怎麼實做出來orz ) : ====================================================== : 對戰表大概是 (假設是六關八小) : 時段一時段二時段三時段四時段五時段六 : 第一關 1vs2 休關休關 : 第二關 3vs4 休關休關 : 第三關休關休關 : 第四關 5vs6 休關休關 : 第五關 7vs8 休關休關 : 第六關休關休關 : ====================================================== : 先謝謝大家:D -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.135.203.156