Добрый день, коллеги.
Помогите решить прикладную задачку. На рисунке изображен потолок балкона.
https://drive.google.com/file/d/1MAmOT1doV1RHlhvXq5rTsxfbti8cstXD/view?usp=sharing

Этот потолок нужно обшить панелями. Размер панели 3000 х 250 (но ширина панели в этой задаче роли не играет). Для обшивки необходимо разрезать панели на части. Эти части, вместе с размерами изображены на картинке. Так как потолок имеет сложную форму, эти части получаются разными по длине. Подскажите пожалуйста, как раскроить панели так, чтобы не было обрезков (это в идеале) или чтобы минимизировать обрезки (более реальный вариант)?
Может кто-то уже решал подобную задачу? В интернете полно методик и алгоритмов оптимизации и минимизации, но нет (или я не нашел) готовых решений для моей задачи. Я конечно же могу написать какой-то алгоритм подбора, но работать он будет ооооочень долго (больше триллиона комбинаций), да и на его написание и отладку потребуется какое-то время. В общем это будет из пушки по воробьям.
То есть интересует какое-то решение, легко применимое на практике.
Ну возможно какой-то не сложный алгоритм, который можно реализовать на коленке в Экселе за 15 минут.

У тебя выпуклые грани. Без обрезков не получится

(1) Ну это неизбежные обрезки. Даже если бы они были не выпуклые, то совсем без обрезков вряд-ли получится. Хотелось бы их минимизировать.

+ (2) Для упрощения считаем, что все куски прямоугольные.

(0) некрасиво будет если делать стык полос по длине. Нужно одну полосу на всю ширину балкона. Поэтому отходов будет больше чем предполагаешь

Вырежи из бумаги уменьшенную копию, разложи на столе и комбинируй. Найдешь какой-то оптимальный вариант довольно быстро.

Cutting3

Сам ищи в гугле, здесь ссылки на варез давать нельзя

(5) Нет,лучше пусть с пластелина лепит и сюда фотку выложит.

(4) Если делать в длину, такие куски во первых сложней монтировать, во вторых длина балкона больше длины панелей и все равно придется стыковать - будет еще некрасивей.

(7) Я не прошу ссылки. Я прошу методику.

(0) Делай так, чтобы сумма длины 2 или 3 элементов была максимально близка к 3000 (например, остается обрезок не более 5 см). Убирай эти кусочки из общей кучи. Ну и так пока не расположишь все куски. Далее смотри, сколько лишних панелей требуется. Если ни одной лишней - считай задача решена.

(9) Под длиной и имел ввиду сторону с размером 1560

(8) Могу фотку выложить, когда потолок сделаю.

(11) так это ж рюкзачок :)

(11) Еще бы методику подбора элементов, цены б не было твоему совету. В это все и упирается, что слишком много комбинаций.

(11) Программа примерно так и делает, не поверишь.
(10) За что ты презираешь программы? Программа и есть методика.

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

(13) Выложи фотку когда программу Cutting установишь, блин, сейчас сам твои размеры забью и ответ тебе покажу

(18) Ок, давай. такой вариант тоже подойдет.

(10) самая оптимальная методика - разрезаешь свои панели на мааааааленькие кусочки и собираешь аки из мозаики

(17) 15 кусков - это больше триллиона комбинаций.

625+710 + длинная - одна панель
795+880 + длинная - вторая панель
1050+965 + 700 - еще панель.
700+700 + длинный кусок
остальное пополам.
Просто на практике идеально вымеренное не сделаешь - запутаешься быстрее.

(15) У тебя общая длина 15,21 м. Соответственно, ты купишь 6 панелей длиной 18 м. Далее чисто интуитивно складывай. Найдешь какое-то решение. Узнаешь, какие обрезки остаются - и решишь, устраивает тебя это, либо надо перекомбинировать панели, чтобы получить обрезок большей длины (т.е. который может куда-то еще пригодиться).

Делайте жадным алгоритмом: упорядочив по убыванию длины, подбираете, пока влезает. Если получатся большие остатки - попробовать улучшить.

Херня, 6 полос
880+625+700+700
1305+965+710
1050++1220+700
1560+1390
1135+1475
700

1 обрезок 390 и 1 обрезок 2300

Лучше не получится.

Только один оптимальный вариант

ширину распила не учитываем?

4 мм

(29) Можно не учитывать - пластик можно ножом разрезать.

(25) Похоже на правду. Проверять я, конечно же, не буду :)

+ (31) Даже если пилить ножовкой, то края-то все равно уголком закрывать, так что плюс/минус миллиметр роли не играет.

(25) Спасибо. Все примерно так и есть.

1560+ 1390
1470+700+700
1305+710+965
1220+8/80+700
1135+1050+795
625

(32) Каттинг лучший в мире для всяких ДСП

(21) Сколько там у тебя полос будет? 50 полос максимум. Вручную можно перебрать длинны, интуитивно

(35) 1220+880+700 - не оптимально.

(37) Полос будет 15. Интуитивно не интересно, интересно минимизировать обрезки.

(39) тебе предложили 2 варианта. Всеравно в любом случае нужно 6 полос как не крути

(25) [режим зануды] Где 795?

остатки в мм
1-50
2-130
3-20
4-200
5-20

самое что ни есть оптимальное. : доска запасная а то вдруг после пивасика не так померяещь:)

(38) Зато остается обрезок 2375, а не 2300.

(41) В первом неправильно перепечатал:
880+625+795+700
1305+965+710
1050++1220+700
1560+1390
1135+1475
700

на стройку один хрен надо с запасом брать, а то потом цвет хрен подберешь из другой партии. я в 2013 ламинат у себя стелил так на гардеробе 3 пачки до сих пор лежит

(39) Эти задачи за приемлемое время решаются именно что интуитивно. Т.е. с нечеткой логикой.

(44) Первая панель ровно 3000, на распил нет запаса.

Да, Супер оптимизация.

в (44) отходов 490 мм - 5 досок
у меня 420 мм - 5 досок

Экологичненько...

Если сантиметрами меряться то у меня длиннее. Я выиграл

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

(0) В задаче не хватает длины минимального куска
Данное условие уменьшит количество решений и обрезков

+(52) плюс ограничение по количеству стыков по длине, ещё урежет количество решений.

Короче когда полностью поставишь задачу, там уже не будет триллион вариантов.

(0) помню ложил в квартире доску паркетную, два цвета.
рассчитал в Екселе с учетом коробки 227 см и 115 см. Точные размеры уже не помню ну короче в длинной и короткой упаковке Таркет. По подсчетам покупка длинной упаковки с условием полных коробок давало преимущество.
Купил, привез, начал укладку. Первую коробку вскрыл - всё нормально, вторую вскрыл, а там вместо двух длинных - 4 коротких. Упс.....
Пришлось пересчитывать с учетом вновь открывшихся обстоятельств. :)

(52) Там на картинке все куски есть, как минимальные, так и максимальные. А триллион вариантов - это количество всех перестановок для 15-ти кусков, если решать задачу тупым перебором.

2(45)Запасливый. :)
Мне плитку в ванну считали с запасом - две коробки до сих пор в гараже валяется, всё везде пересчитывал сам.

(55) Ты не понял. Почитай рекомендацию например по укладки ламината. Там ты поймешь про минимальный кусок.
Про количество стыков - это минимально или максимально (а панели стыкуются по длине?)
И начать укладку можно с трёх точек - лево, право и с произвольной в две стороны (третий вариант может быть технически не возможен) Старт определяет дальнейшую логику.

2(55) В реале не поверю про триллион вариантов.
По опыту выкладки плитки, паркета, ПВХ плитки, обоев - оптимальное решение - одно.

(56) У меня с плиткой тоже прикол получился. В магазине все посчитали с небольшим запасом. Должно было остаться несколько плиток. Пришел мастер, выложил плитку, осталась лишняя коробка. Вот так вот он соптимизировал, без потери качества :)
(57) Да все я понял. Панели по длине не стыкуются - смотри рисунок. У меня укладывать либо слева направо, либо справа налево, других вариантов нет.

(58) В реале триллион вариантов никто и не собирался перебирать :)

2(59) Если панели по длине не стыкуются то решение то одно
Сначала режутся длинные более 1/2 длины панели и понеслось в низ.
Или ты хочешь получить СЛУ по данной задаче?

(61) Я хочу сэкономить :)

2(62) Если не стыкуются, то врятли.
Просто если стыкуются, там немного другая логика, плюс левый/правый кусок для стыка

+ (62) в (44) и (35) уже все посчитали. Похоже у меня лишняя панель останется.

(62) Сейчас подумал что может есть какое то СЛУ плюс решение к нему по оптимизации, но там ширина важна будет.

(64) есть же ещё нюанс по укладке, т.е. первая 250 а последняя 50, Этетичнее положить 2 по 150.

(66) Нету там никаких нюансов, от слова совсем. Посмотри на картинку.

(62) Тогда сократи панели на 1 см с каждой стороны и режь 5 панелей :)

(68) Это как? В чем магический смысл?

+ (69) А, наверно понял твою мысль...
Экономия не получится. Нужно целую панель сэконмить, чтобы обратно в магазин сдать.

(69) Тогда общая длина получится меньше 15 м, и, теоретически, будет существовать решение как разрезать 5 панелей.

(67) по ширине, потому что всегда прикидывают с какой ширины начать, чтобы в конце не закончить 5см шириной

(72) Ну я высчитаю ширину крайних панелей и обрежу их. Спасибо за подсказку, что-то я упустил этот момент из виду, но в любом случае количество кусков не изменится, так как их общая длина больше длины балкона. Просто надо будет резать не только последний, но и первый кусок. Еще раз спасибо за подсказку :)

+ (73) А обрезать я могу только крайние куски, так что даже если получится 5 см, то никуда не денешься, придется оставлять как получилось.

(74) Если останется 5 см - кривизна стены даже на 1 см будет очень видна. Поэтому стараются оставлять куски максимальной ширины.

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

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

(77) Я не понял мы один тип балкона рассматриваем, или задачка гипотетическая с произвольным примером?

(78) Задача вполне конкретная, с конкретным балконом. Все же нарисовано на картинке...

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

(80) Так уже посчитали (44) и (35)

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

Вот что значить иногда ум мешает работе.
Если искать алгоритм будешь долго искать.
Мой брат делает мебель он без всякого там алгоритма быстро все и без отходов (или минимальными) делает разрезы.
Он в математике не силен.
Правда архитектурный заканчивал, но был троечником.
Самый верный самому быстро подобрать оптимальные разрезы

(8) Вот фотка того, что получилось.
https://drive.google.com/open?id=1MoeatMGi6ih-9DsC6r9q4x20azialEYv
Спасибо всем за помощь.