作者bleed1979 (十三)
站内Prob_Solve
标题[请益] Banzhaf Power Index
时间Thu Jun 17 06:54:39 2010
想请教计算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
1F：→ DJWS:430 -> dynamic programming 435 -> backtracking 06/17 16:36
2F：→ bleed1979:嗯，AC了。类似於背包，但我把重量(加总)放在外圈， 06/17 22:38
3F：→ bleed1979:但是花了大把时间在回溯确认总和减去某i是否小於门槛。 06/17 22:39
4F：→ bleed1979:还是得想加速的方法，这两题我用同样的code解。 06/17 22:40
5F：→ DJWS:排序! 06/17 23:12
6F：→ bleed1979:其实我是排序後才过的，和排行榜上的速度差了10几倍。 06/18 10:41
7F：→ bleed1979:方法应该是对的，但想不出加速的办法。 06/18 10:41
8F：→ DJWS:这两题有一样吗? @@" 06/18 14:35