java - 重新混合单词以在一行中容纳最多单词，并使用Java创建更少的行

重新洗牌单词以容纳42个字符的单行中的最大单词数，并使用Java创建较少的行数
我必须创建逗号分隔的单词，一行的最大大小是42。
字符串可以以这样的方式重新洗牌，以容纳最大字数，而不交叉行大小42，行数更少。
为了达到这个目的，我根据单词的长度对其进行了排序。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ManageWords {
private static final int LINE_MAX_SIZE = 45;

public static void main(String[] args) {
List<String> wordList = new ArrayList<String>();
wordList.add("URUNDI");
wordList.add("AFGHANISTAN");
wordList.add("WEST GERMANY");
wordList.add("ALAND ISLANDS");
wordList.add("VIET-NAM - DEMOCRATIC REPUBLIC OF");

Collections.sort(wordList, Comparator.comparingInt(String::length));
List<String> concatenatedWordsLines = new ArrayList<String>();

for (int i = 0; i < wordList.size(); i++) {
String concatenatedWords = wordList.get(i);
int j = i + 1;

if (concatenatedWords.length() < LINE_MAX_SIZE) {
while (concatenatedWords.length() < LINE_MAX_SIZE && j <= wordList.size() - 1) {
if (concatenatedWords.concat("," + wordList.get(j)).length() < LINE_MAX_SIZE) {
concatenatedWords = concatenatedWords.concat("," + wordList.get(j));
} else {
break;
}
j++;
}

concatenatedWordsLines.add(concatenatedWords);
i = j - 1;
}
}

for (String s : concatenatedWordsLines) {
System.out.println(s + " : " + s.length());
}
}
}

在上面的代码中，我用3行代码得到下面的结果，

 
    URUNDI,AFGHANISTAN,WEST GERMANY
    ALAND ISLANDS
    VIET-NAM - DEMOCRATIC REPUBLIC OF
    

Whereas I am expecting it in 2 lines which size is less than or equal to 42 like below,

 
    URUNDI,VIET-NAM - DEMOCRATIC REPUBLIC OF
    AFGHANISTAN,WEST GERMANY,ALAND ISLANDS
    

目的是用最少的行容纳所有的单词。

最佳答案

你的问题是bin-packing problem的变体这是一个np难问题，所以除非你的输入很小，否则试图找到一个最优解可能是不可行的。
有几种解决方法：
你可以选择一个first-fit greedy algorithm（很容易实现，在很多情况下都能给出不错的结果）。这是问题的两个近似值，所以在最坏的情况下，你将有两倍以上的线比最好的解决方案。
您还可以实现一个蛮力算法（使用枚举算法测试所有可能的组合，只适合非常小的输入，但找到一个最佳的解决方案）。
使用java的另一种可能性是使用类似于Cplex solver的接口将其插入ILP（或任何其他Ilog解算器）。
imho，ilp方法应该受到青睐，因为它是一个学习使用的有用工具，一旦你完成了接口部分，程序将非常容易编写，而且它已经被优化了，并将在小实例上为你返回一个最佳答案，对于不可处理的实例返回一个很好的可行解决方案。