[請益] Banzhaf Power Index (已解決，感謝D大)
看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/06/17 06:54)推噓0(0推 0噓 8→)留言8則, 2人參與討論串1/1
想請教計算Banzhaf Power Index是否有多項式時間的解。
我嘗試搜goole，關鍵字包括︰
"Banzhaf Indices"
"C++ Banzhaf Indices"
"Banzhaf Indices Dynamic Programming"
等等，類似的組合字眼都用上。
相關文件的閱讀上，比較多是時間複雜度的推導。
鮮少有一個高效的演算法來解決問題。
主要是碰到了ACM UVa 430 和 435 這兩題，卡關了。
目前解法是暴力解和dfs，但都TLE。
曾下載了open source來啃，發現還是暴力的解法，速度不夠快。
比如測資︰
門檻 單位票數
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
上面的單位有27個，每一個都可以過門檻。即使不合理，卻可能是測資。
在Uva的forum上有人提到，用fancier algorithm解題的，但相關資訊似乎很缺乏。
希望有高手能提點一下對這個主題的知識，謝謝。
Bleed
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.124.240
→
06/17 16:36, , 1F
06/17 16:36, 1F
→
06/17 22:38, , 2F
06/17 22:38, 2F
→
06/17 22:39, , 3F
06/17 22:39, 3F
→
06/17 22:40, , 4F
06/17 22:40, 4F
→
06/17 23:12, , 5F
06/17 23:12, 5F
→
06/18 10:41, , 6F
06/18 10:41, 6F
→
06/18 10:41, , 7F
06/18 10:41, 7F
→
06/18 14:35, , 8F
06/18 14:35, 8F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12