Перетасуйте слова, чтобы разместить максимальное количество слов в одной строке размером 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
В то время как я ожидаю это в 2 строках, размер которых меньше или равен 42, как показано ниже,
URUNDI,VIET-NAM - DEMOCRATIC REPUBLIC OF
AFGHANISTAN,WEST GERMANY,ALAND ISLANDS
Цель состоит в том, чтобы разместить все слова с минимально возможными строками.
Ваша проблема является вариантом проблема с бин-упаковкой. Это NP-сложная задача, поэтому, если ваши входные данные не очень малы, попытка найти оптимальное решение может оказаться неосуществимой.
Есть несколько способов ее решения:
Вы можете выбрать жадный алгоритм первого подгонки (просто реализовать, во многих случаях может дать достойные результаты). Это 2-аппроксимация задачи, поэтому в худшем случае у вас будет в два раза больше строк, чем в наилучшем возможном решении.
Вы также можете реализовать алгоритм грубой силы (проверить все возможные комбинации с помощью алгоритма перечисления, подходит только для очень маленьких входных данных, но находит оптимальное решение).
Другой возможностью использования java было бы подключение его к Комплексный решатель (или любому другому решателю НЛП) с использованием интерфейса, такого как Илог.
ИМХО, следует отдать предпочтение подходу ILP, так как это полезный инструмент для изучения, программы будут довольно просты для написания, как только вы закончите с интерфейсной частью, и он уже оптимизирован и даст вам оптимальный ответ на небольшие экземпляры и хорошее возможное решение для неразрешимых экземпляров.