rstJkee
@rstJkee

Задачи с минимальными и максимальным вариантами и неравномерными выборками?

Дайти, пожалуйста, ссылки на материал, как решать такие шаблоны (теорию):
Имеется n досок, нужно построить забор из m досок, при этом забор должен быть максимально возможным по высоте (доски можно распиливать нацело (то есть int)), каждая i доска имеет Xi высоту.


То есть, на входе
8 - сколько должно быть в заборе досок, 4 - сколько есть
x1, x2, x3, x4 - сами доски (вернее их высоты)

Задачки интересными кажутся, поэтому хочется теорию подтянуть
  • Вопрос задан
  • 63 просмотра
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Такие задачи часто решаются дихотомией + жадным агоритмом, как в этом примере (надо бинарным поиском перебирать ответ, а дальше смотреть, можно ли нужное количество досок заданной длины получить из исходных).

Какой-то общей теории я вспомнить не могу. Все-таки при дискретной оптимизации очень много разных задач. Могу только посоветовать посмотреть жадные алгоритмы. Обязательно кроме решений научитесь доказывать решения и почему жадность в каждом конкретном случае работает.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы