[問題] Letter Lock Picking Puzzle

[FRAXIS (喔喔)]

http://puzzles.bostonpython.com/lock.html 從這上面看的

密碼鎖總共有 N 個環，每個環上面有 K 個字母。
同時給定一個字典，字典內每個單字的長度都為 N 。

要如何設計每個環上的字母，使得可以用密碼所表示的單字數量最大。

有比較好的演算法可以解決這問題嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.23.200.172
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1480224680.A.986.html
推 cutekid: 有趣的問題！想知道 + 1
推 outofyou: 這跟背包問題有關嗎？
→ outofyou: 發現不行，因為可能跟別的單字有重複的字母。
→ outofyou: 想知道 + 1， O( 26^N * 單字數 )
→ outofyou:                 ^^^ 錯了，是 O( (26取K)^N * 單字數)
推 aaaaajack: 找二分圖是否包含給定大小完全圖似乎是NP-complete
→ aaaaajack: 所以應該N=2就很難做了 (假設字母集跟K很大)
→ FRAXIS: 看來 balanced biclique problem 可以 reduce 到這問題
→ FRAXIS: 而 balanced biclique problem 在 bipartite graph 是 NPC
→ aaaaajack: 不過字母集是常數的case可能可以考慮 但我還沒有想法
→ FRAXIS: 字母集大小是常數的話窮舉就是 polynomial time 了
→ aaaaajack: 沒有吧 窮舉是c^N ?
→ FRAXIS: 喔對 我搞錯了