[问题] Letter Lock Picking Puzzle FRAXIS PTT批踢踢实业坊

楼主: FRAXIS (喔喔) 2016-11-27 13:31:17

http://puzzles.bostonpython.com/lock.html 从这上面看的
密码锁总共有 N 个环，每个环上面有 K 个字母。
同时给定一个字典，字典内每个单字的长度都为 N 。
要如何设计每个环上的字母，使得可以用密码所表示的单字数量最大。
有比较好的算法可以解决这问题吗？

作者: cutekid (可爱小孩子) 2016-11-28 15:22:00

有趣的问题！想知道 + 1

作者: outofyou 2016-11-28 20:21:00

这跟背包问题有关吗？发现不行，因为可能跟别的单字有重复的字母。想知道 + 1， O( 26^N * 单字数 )^^^ 错了，是 O( (26取K)^N * 单字数)

作者: aaaaajack (丁丁是个人才) 2016-12-02 01:08:00

找二分图是否包含给定大小完全图似乎是NP-complete所以应该N=2就很难做了 (假设字母集跟K很大)

楼主: FRAXIS (喔喔) 2016-12-02 10:07:00

看来 balanced biclique problem 可以 reduce 到这问题而 balanced biclique problem 在 bipartite graph 是 NPC

作者: aaaaajack (丁丁是个人才) 2016-12-03 01:29:00

不过字母集是常数的case可能可以考虑但我还没有想法

楼主: FRAXIS (喔喔) 2016-12-03 10:31:00

字母集大小是常数的话穷举就是 polynomial time 了

作者: aaaaajack (丁丁是个人才) 2016-12-03 18:58:00

没有吧穷举是c^N ?

楼主: FRAXIS (喔喔) 2016-12-03 21:30:00

喔对我搞错了

继续阅读