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 ?

喔对 我搞错了