作者FRAXIS (喔喔)
看板Prob_Solve
標題[問題] Letter Lock Picking Puzzle
時間Sun Nov 27 13:31:17 2016
http://puzzles.bostonpython.com/lock.html 從這上面看的
密碼鎖總共有 N 個環，每個環上面有 K 個字母。
同時給定一個字典，字典內每個單字的長度都為 N 。
要如何設計每個環上的字母，使得可以用密碼所表示的單字數量最大。
有比較好的演算法可以解決這問題嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.23.200.172
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1480224680.A.986.html
1F：推 cutekid: 有趣的問題！想知道 + 1 11/28 15:22
2F：推 outofyou: 這跟背包問題有關嗎？ 11/28 20:21
3F：→ outofyou: 發現不行，因為可能跟別的單字有重複的字母。 11/28 21:24
4F：→ outofyou: 想知道 + 1， O( 26^N * 單字數 ) 11/28 21:28
5F：→ outofyou: ^^^ 錯了，是 O( (26取K)^N * 單字數) 11/28 21:41
6F：推 aaaaajack: 找二分圖是否包含給定大小完全圖似乎是NP-complete 12/02 01:08
7F：→ aaaaajack: 所以應該N=2就很難做了 (假設字母集跟K很大) 12/02 01:09
8F：→ FRAXIS: 看來 balanced biclique problem 可以 reduce 到這問題 12/02 10:07
9F：→ FRAXIS: 而 balanced biclique problem 在 bipartite graph 是 NPC 12/02 10:07
10F：→ aaaaajack: 不過字母集是常數的case可能可以考慮 但我還沒有想法 12/03 01:29
11F：→ FRAXIS: 字母集大小是常數的話窮舉就是 polynomial time 了 12/03 10:31
12F：→ aaaaajack: 沒有吧 窮舉是c^N ? 12/03 18:58
13F：→ FRAXIS: 喔對 我搞錯了 12/03 21:30