string - 算法:将较小的字符串最佳地组合在一起以生成指定长度的较长字符串？

Question

一般问题

我有一组短字符串，每个字符串的长度都不同，最小值 X > 0 和最大值 Y。什么算法可以将这些短字符串最佳地组合在一起以生成长度为 M 的长字符串，其中 M >> Y？最优将被定义为长度尽可能接近 M 的长字符串的最大数量。

详情

我正在编写推文创建器来练习 javascript。我有一个问候语列表和一个帐户名列表。我希望我的程序创建推文，这样每条推文都有一个问候语，其余字符用于帐户名。每条推文不得超过 140 个字符。

Hello! @person1 @acc2 @mygoodfriend3 ...

当然，每个帐户的字符数都不同。我希望通过优化选择帐户名称组合，每条推文尽可能多地使用 140 个字符。

我很确定有一类已知的问题/算法可以解决这个问题，但我不记得了。

Answer 1

这种问题叫做knapsack problem ，而精确(或完全最优)的解决方案以难以处理而闻名。

但是，有合理的近似求解器，以及“伪多项式时间”动态规划算法。