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

Question

[arklight]

Дайти, пожалуйста, ссылки на материал, как решать такие шаблоны (теорию):

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

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

Задачки интересными кажутся, поэтому хочется теорию подтянуть

Comments

[arklight]

Bavashi, нет, зачем же. Может быть как N больше M, так и N меньше M. Например: 5 досок - нужно, 10 досок - есть, но высоты не очень большие (то есть можно в 2 раза повысить высоту, если учесть, что доски равны по высоте) или 10 досок - нужно, 5 - есть => можно каждую доску пополам поделить и будет не 5, а 10

[arklight]

Bavashi, в этом и весь интерес. То есть доски можно пилить на int длину. То есть, нужно забор из 3 досок, а есть 2 по 50 метров. Надо найти максимальную высоту забора. И вот сиди и пили эти доски, а как и какими алгоритмами - хз)))

[arklight]

Bavashi, 100, 100 - чётные, 93 - делим нацело на 2, получаем 46 вроде. То есть, остаётся 47 в запасе

[arklight]

Bavashi, блин, по моему там вообще про такое ничего не было. Только про максимальную высоту говорили. Наверно без остатка

[arklight]

Bavashi, хм, я думал где-то написал, что если что-то нереальное, по типу "нужно 10 досок, а есть 1 и та 9 метров в высоту", то нужно вывести 0

[arklight]

Смотри, вот ссылка на задачу: vtcloud9.ulstu.ru/ru/problem-pid-c53a?ps=1&smt=a&s... . Думаю, так станет меньше вопросов, ибо мб я что-то не так формулирую

Answer 1

[Wataru]

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

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