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

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

3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
1
0
54
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

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

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

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

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

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

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

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

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