Write More Bits

从n个单词中选最大数量的单词（cardinalality of subset of these n words)放到k行中，每行长度为L，但是单词的顺序不能变。知道每个单词的长度l_{i}。 设计一个算法，要求复杂度和L 无关。

乍一看，如果将每行长度L看作背包问题的容量，每个单词的长度看作物品的重量，每个单词的value都是1，貌似排列每一行都是一个背包问题。但是，一个所有物品value都为1的背包问题，已经不再是一个NPC问题了。可以用贪心算法解决，呵呵…而这一点正是，这个题目的关键…
将所有单词按照顺序编号1－n，当计算前k个单词放在一行最多能放多少个的时候，可以通过一个贪心遍历完成：

如果当前行剩余的长度能存放当前单词，则放下；
如果不能，则
     找到当前行最长的单词和当前单词比较，留下较短的

我们可以通过使用最大堆来保存已放在当前行的元素的长度，来加快程序寻找最长单词的过程。有了在O(n*lgn)时间能完成的，放置一行单词的算法之后，我们可以在此基础上，作动态规划，完成这个题目。

dp(k,n) = Max(for every j, 1<j<n){
                         dp(k-1, n-j)+m (m 是j个单词中能放在当前行的数目)
                }

dp产生的子问题数目是n*k个，每个问题的选择数目是n个，所以总体复杂度n*n*k.

Filed under:
编程＆算法 by Yang Bo