给出一个包含字母az至少一次的单词列表,你会如何编写一个程序来找到由字符数(不计算空格)计算的最短的pangram作为单词的组合？
由于我不确定是否存在简短的答案,这不是代码高尔夫,而只是讨论如何处理这个问题.但是,如果你认为你可以设法写一个可以做到这一点的短程序,那么继续吧,这可能会变成代码高尔夫:)
我会通过证明问题是NP难的,并通过检查启发式查看类似的NP难题来解决这个问题.
我们可以减少Set Cover问题.Set Cover的不同之处在于没有使用多少字母,但是使用的字数最小化.假设我们要解决集合覆盖问题,给出N个字,每个长度小于M的让我们通过克隆给定的建立另一套的话,但串接他们每个人N*M个非英文字母,也就是说,Ж.的 如果我们可以构建一个需要最小符号的pangram(在a,b,c ... x,y,z,ж字母表上),那么如果我们删除所有Ж字母,那将是一个具有最少单词的pangram.
这证明,原来的问题是NP难的,但不幸的是,我们需要减少对一些NP难问题重用它(希望已经知道)启发式.设置封面与对数近似贪心试探法,但我不认为它适用于原问题(设置覆盖问题的性质,需要服用富含信,长的话,它不是解决我们问题的办法).
所以我会搜索相关的NP难题列表,并检查是否有兴趣.这就是我接近这个的方法.