java - 重新排列单词以在一行中容纳最大单词数并使用 Java 创建更少的行数

Question

重新排列单词以在一行 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
    

目的是用尽可能少的行容纳所有单词。

Answer 1

您的问题是 bin-packing problem 的变体.这是一个 NP 难问题，因此除非您的输入非常小，否则尝试找到最佳解决方案可能不可行。

有几种方法可以解决:

• 你可以去找一个first-fit greedy algorithm (易于实现，在许多情况下可以给出不错的结果)。它是问题的 2 近似值，因此在最坏的情况下，您的行数将是最佳解决方案的两倍。

• 您还可以实现蛮力算法(使用枚举算法测试所有可能的组合，仅适合非常小的输入但找到最佳解决方案)。

• 另一种使用 java 的可能性是用 Cplex solver 插入它(或任何其他 ILP 求解器)使用类似 Ilog 的界面.

  恕我直言，ILP 方法应该受到青睐，因为它是一种学习使用的有用工具，一旦您完成了接口(interface)部分，程序将非常容易编写，并且它已经过优化并将返回给您小实例的最佳答案，以及不可处理实例的良好可行解决方案。