Отобрать элементы массива, которые в сумме соответствуют условию

Есть расстояние между городами
ls = [51, 56, 58, 59, 61]

Нужно отобрать все варианты комбинаций городов, расстояние между которыми не больше t = 174

  • t (максимальная сума расстояний, целое >= 0),
  • k (количество городов, k> = 1),
  • ls (список расстояний),

вот основное тело кода

const chooseOptimalDistance = (t, k, ls) => {
// код
return null;
}

chooseOptimalDistance(174, 3, [51, 56, 58, 59, 61]); //173
chooseOptimalDistance(163, 3, [50]); // null

как отобрать ?

может использовать reduce с условием ?..

Сперва лирика. Мне кажется это странный выбор чтобы моделировать расстояния между городами. Есть у меня подозрение что невозможно расставить города так чтобы получить такой набор значений. Тем не менее думаю что это не имеет значения для того что требуется от подхода к решению. Поправь если я описываю что-то не так.

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

  1. Нужен цикл (назовем его ЦИКЛ_1). В начале цикла создай массив куда будем складывать результаты, назовем его РЕЗУЛЬТАТЫ. КОМБИНАЦИЯ будет на каждой итерации создавать возможную комбинацию, назовем КОМБИНАЦИЯ, из расстояний (а это значит будет второй вложенный цикл, назовем его ЦИКЛ_2, для генерации комбинации), с учетом лимита k. При реализации обрати внимание что КОМБИНАЦИЯ [10, 20] это то же самое что и КОБИНАЦИЯ [20, 10].
  2. Внутри ЦИКЛ_1 проверяй удовлетворяет ли КОМБИНАЦИЯ условию (сумма элементов меньше чем t), если удовлетворяет, складывай ее в РЕЗУЛЬТАТЫ.

Не ожидай что на этом форуме тебе подскажут сразу готовое решение задачи. Скорее помогут сдвинутся с мертвой точки.

1 симпатия

вот например функция создания нового масива,
arr.filter(callback[, thisArg])
но как прописать перебор всех комбинаций просто…

Это не функция. Это кусок кода из документации. Ты сам что успел попробовать/надумать?

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

у меня только самое грубое решение - создать цикл, в котором перебирать массив, и заносить подходящие условию результаты в новый массив.
но это как то не по фен-шуйному… много кода для простой задачи

Я отвечу историей.

Когда я учился в универе у нас была домашняя задача найти такую расстановку ферзей чтобы 8 штук на шахматной доске не били друг друга. Я подумал что это слишком “глупо” решать задачу перебором всех возможных вариаций. Потратил все время на поиск другого решения, но его не нашел и задачу не решил.

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

Итого - пиши решение тем подходом что знаешь. Лучшие подходы узнаешь позже, у тебя будет время их применить. Написанная неэффективно задача лучше ненаписанной эффективной.

2 симпатии