[請益] Banzhaf Power Index

[bleed1979 (十三)]

想請教計算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
→ DJWS:430 -> dynamic programming  435 -> backtracking
→ bleed1979:嗯，AC了。類似於背包，但我把重量(加總)放在外圈，
→ bleed1979:但是花了大把時間在回溯確認總和減去某i是否小於門檻。
→ bleed1979:還是得想加速的方法，這兩題我用同樣的code解。
→ DJWS:排序!
→ bleed1979:其實我是排序後才過的，和排行榜上的速度差了10幾倍。
→ bleed1979:方法應該是對的，但想不出加速的辦法。
→ DJWS:這兩題有一樣嗎? @@"