作者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/cn.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