http://puzzles.bostonpython.com/lock.html 從這上面看的
密碼鎖總共有 N 個環，每個環上面有 K 個字母。
同時給定一個字典，字典內每個單字的長度都為 N 。
要如何設計每個環上的字母，使得可以用密碼所表示的單字數量最大。
有比較好的演算法可以解決這問題嗎？

有趣的問題！想知道 + 1

這跟背包問題有關嗎？發現不行，因為可能跟別的單字有重複的字母。想知道 + 1， O( 26^N * 單字數 )^^^ 錯了，是 O( (26取K)^N * 單字數)

找二分圖是否包含給定大小完全圖似乎是NP-complete所以應該N=2就很難做了 (假設字母集跟K很大)

看來 balanced biclique problem 可以 reduce 到這問題而 balanced biclique problem 在 bipartite graph 是 NPC

不過字母集是常數的case可能可以考慮 但我還沒有想法

字母集大小是常數的話窮舉就是 polynomial time 了

沒有吧 窮舉是c^N ?

喔對 我搞錯了