Поиск комбинаций отрезков. - Помощь студентам

Alecs-ok99 · 13.04.2016, 01:40

Есть одномерные детали длиной 3,5,7,9,11,13,15. Количество деталей каждого размера - бесконечность.
Есть заготовка фиксированной длины 20.
Припуски, толщина распила 0.
Как получить все возможные комбинации полного заполнения заготовки?
То есть интересуют все комбинации типа :
5+15 = 20
3+3+5+9 = 20
7+13 = 20
3+3+3+3+3+5 = 20

Ручками - не реально, размеров деталей намного больше. Здесь все упростил, суть не меняется

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

theYozh · 13.04.2016, 02:10

Цитата:

деталей намного больше

Больше чем что? чем рук?)

phomm · 13.04.2016, 05:35

Надо гуглить "задача\алгоритм (оптимального) заполнения рюкзака"

Serge_Bliznykov · 13.04.2016, 10:05

посмотрите, на форуме решалась такая задача:
Набрать сумму чисел (Delphi)

ещё похожая задача:
http://programmersforum.ru/showthread.php?t=233944

evg_m · 13.04.2016, 11:07

рекурсией по длине остатка и с упорядоченным (в любую сторону) массивом длин деталей.
очень похожая тема
заготовка =стена (и даже без дырок)
деталь =блок (их даже и не ограниченное количество) и их НЕ надо вертеть и НЕ надо перемещать в разные позиции.

а упорядоченность исходного массива длин деталей позволит сократить перебор. и избежать дублей! (1+2+3; 2+1+3; 3+1+2; 3+2+1; 1+3+2; 2+1+3; )
используя следующее правило. Располагать детали в заготовке в том же порядке длин деталей, что и исходный массив.

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

Alecs-ok99 · 13.04.2016, 22:12

Спасибо за ответы, разберусь с ссылками, покопаю вокруг.

Serge_Bliznykov · 14.04.2016, 09:40

Alecs-ok99, а скажите, сколько разных видов деталей у Вас может быть?
Длина суммарная (которая в примере 20) всегда одна и та же или её можно задавать?

13.04.2016, 01:40	#1
Alecs-ok99 Пользователь Регистрация: 05.11.2008 Сообщений: 15	Поиск комбинаций отрезков. Есть одномерные детали длиной 3,5,7,9,11,13,15. Количество деталей каждого размера - бесконечность. Есть заготовка фиксированной длины 20. Припуски, толщина распила 0. Как получить все возможные комбинации полного заполнения заготовки? То есть интересуют все комбинации типа : 5+15 = 20 3+3+5+9 = 20 7+13 = 20 3+3+3+3+3+5 = 20 Ручками - не реально, размеров деталей намного больше. Здесь все упростил, суть не меняется Подскажите куда копать, интересует сам алгоритм, с какой стороны подойти. Буду благодарен за любые ответы в тему. Последний раз редактировалось Alecs-ok99; 13.04.2016 в 08:26. Причина: уточнение формулировки вопроса

13.04.2016, 05:35	#3
phomm personality Старожил Регистрация: 28.04.2009 Сообщений: 2,899	Надо гуглить "задача\алгоритм (оптимального) заполнения рюкзака" My projects (Mirror) github telegram

13.04.2016, 10:05	#4
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	посмотрите, на форуме решалась такая задача: Набрать сумму чисел (Delphi) ещё похожая задача: http://programmersforum.ru/showthread.php?t=233944 Последний раз редактировалось Serge_Bliznykov; 13.04.2016 в 10:16.

13.04.2016, 11:07	#5
evg_m Старожил Регистрация: 20.04.2008 Сообщений: 5,543	рекурсией по длине остатка и с упорядоченным (в любую сторону) массивом длин деталей. очень похожая тема заготовка =стена (и даже без дырок) деталь =блок (их даже и не ограниченное количество) и их НЕ надо вертеть и НЕ надо перемещать в разные позиции. а упорядоченность исходного массива длин деталей позволит сократить перебор. и избежать дублей! (1+2+3; 2+1+3; 3+1+2; 3+2+1; 1+3+2; 2+1+3; ) используя следующее правило. Располагать детали в заготовке в том же порядке длин деталей, что и исходный массив. В этом случае из последующих (ниже по рекурсии) переборов исключаются те детали которые лежат в исходном массиве раньше последней уложенной. (как бы ограничение на количество деталей). программа — запись алгоритма на языке понятном транслятору Последний раз редактировалось evg_m; 13.04.2016 в 11:13.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
поиск возможных комбинаций из заданного диапазона	jedi1320	Софт	7	16.02.2016 08:36
таблица комбинаций	Игорь_С	Общие вопросы C/C++	1	11.01.2013 15:26
Перебор комбинаций	KobolD	Помощь студентам	10	17.03.2011 12:37
Вычисление множества комбинаций	phobia	Помощь студентам	3	17.11.2010 10:56
Delphi. Проверка комбинаций	Zhamie	Помощь студентам	7	15.09.2009 11:39

13.04.2016, 22:12	#6
Alecs-ok99 Пользователь Регистрация: 05.11.2008 Сообщений: 15	Спасибо за ответы, разберусь с ссылками, покопаю вокруг.

14.04.2016, 09:40	#7
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	Alecs-ok99, а скажите, сколько разных видов деталей у Вас может быть? Длина суммарная (которая в примере 20) всегда одна и та же или её можно задавать?