Перетасуйте слова, чтобы разместить максимальное количество слов в одной строке и создать меньшее количество строк с помощью 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
    

В то время как я ожидаю это в 2 строках, размер которых меньше или равен 42, как показано ниже,


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

Цель состоит в том, чтобы разместить все слова с минимально возможными строками.

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
1
0
54
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Ваша проблема является вариантом проблема с бин-упаковкой. Это NP-сложная задача, поэтому, если ваши входные данные не очень малы, попытка найти оптимальное решение может оказаться неосуществимой.

Есть несколько способов ее решения:

  • Вы можете выбрать жадный алгоритм первого подгонки (просто реализовать, во многих случаях может дать достойные результаты). Это 2-аппроксимация задачи, поэтому в худшем случае у вас будет в два раза больше строк, чем в наилучшем возможном решении.

  • Вы также можете реализовать алгоритм грубой силы (проверить все возможные комбинации с помощью алгоритма перечисления, подходит только для очень маленьких входных данных, но находит оптимальное решение).

  • Другой возможностью использования java было бы подключение его к Комплексный решатель (или любому другому решателю НЛП) с использованием интерфейса, такого как Илог.

    ИМХО, следует отдать предпочтение подходу ILP, так как это полезный инструмент для изучения, программы будут довольно просты для написания, как только вы закончите с интерфейсной частью, и он уже оптимизирован и даст вам оптимальный ответ на небольшие экземпляры и хорошее возможное решение для неразрешимых экземпляров.

Другие вопросы по теме