Вряд ли, но вдруг коллективный разум подскажет. Вдруг кто в

Question

Вряд ли, но вдруг коллективный разум подскажет. Вдруг кто в

курсе по оптимальному решению
— Есть бесконечное число палок длиной по 5 метров. Вот где-то лежит гора палок таких.
— Есть желаемое число отрезков произвольной длины. Например нужен 1 отрезок в 1 метр, 1 отрезок в 2 метра и 3 отрезка в 3 метра
— Нужно найти наименьшее возможное число палок, в которые можно вместить заданное количество отрезков, таким образом чтобы остатка было как можно меньше.

То есть если мы возьмем просто по порядку и на одной палке разместим отрезок в 1 метр + отрезок в 2 метра, то от первой палки мы получим остаток 2 метра. И придется все следующие 3 отрезка размещать каждый на своей палке. То есть в итоге мы получим 4 использованные палки и 8 метров остатка.

Однако же более оптимально на первой палке разместить 3+1 метр, на второй палке разместить 3+2 метра и на третьей палке разместить отрез в 3 метра. В этом случае мы задействовали всего 3 палки и получим 1 + 0 + 2 = 3 метра остатков.

Решение нужно запрограммировать естественно. Это сильно упрощенная задача. Пока что придумалось размещать сначала большие отрезки, а потом проходить по уже забронированным палкам и пытаться туда втиснуть отрезки поменьше. Однако это тоже не оптимальный вариант, отрезков могут быть и сотни и тысячи, не всегда так удачно как в примере получается. Есть какое нибудь математически обоснованное решение?

#1c #bitrix #cms #programming #russian #software

0

08.08.2017

1 ответов

20 просмотров

Андрей · Accepted Answer

Андрей

это обычная олимпиадная задача за подсказкой / решением в ЛС. Какое отношение к битриксу?

0

08.08.2017

208 похожих чатов

Вряд ли, но вдруг коллективный разум подскажет. Вдруг кто в

1 ответов

Похожие вопросы