Вход | Регистрация

1С:Предприятие :: 1С:Предприятие 8 общая

Разбиение товаров по грузовым местам, помогите с алгоритмом

Разбиение товаров по грузовым местам, помогите с алгоритмом
Я
   barsik123
 
08.08.18 - 22:13
Имеется N-товаров, которые нужно разбить на грузовые места,чтобы каждое грузовое место было меньше заданного объема, которое одинаково для каждого грузового места. Задачка чисто из комбинаторики, надеюсь найдутся светлые головы, которые смогут ее решить. Смысл вот в чем, нужно перебрать все варианты комбинаций товаров, которые можно разложить в грузовые места, например:
для 2-х товаров будут два варианта:
(товар1,Товар2)  - 1 раб. место.
((товар1)+(Товар2)) - 2 раб. места
Для 3-х товаров
1.(Товар1,Товар2,товар3 ) - 1 раб. Место
2. Схема (2+1) -2 раб. Места
(товар1,Товар2)+товар3
(товар1,товар3)+товар2
(товар2,товар3)+товар1
3.Схема (1+1+1)- 3 раб. Места
(товар1)+(товар2)+(товар3)
Для 4-х товаров:
1. (Товар1,Товар2,товар3,товар4) - 1 раб. Место
2. Схема (3+1) - 2 раб. Места (в одном месте 3 товара, во втором 1)
(1,2,3)+(4)
(1,2,4)+(3)
(1,3,4)+(2)
(4,2,3)+(1)
3. Схема (2+2)
(1,2)+(3,4)
(1,3)+(2,4)
(1,4)+(2,1)
4. Схема (2+1+1) – 3-раб места.
(1,2)+(3)+(4)
(1,3)+(2)+(4)
(1,4)+(2)+(3)
(2,3)+(1)+(4)
(3,4)+(1)+(4)
(2,4)+(1)+(3)
5. Схема (1+1+1+1)
(1)+(2)+(3)+(4)

Для 5-ти товаров приведу только схемы (каждая из них раскладывается на комбинации):
1. (1,2,3,4,5) 
2. (4)+(1)     
3. (3)+(2)      
4. (3)+(1)+(1)
5. (2)+(2)+(1)
6. (2)+(1)+(1)+(1)
7. (1)+(1)+(1)+(1)+(1)

Задачку по сравнению грузовых мест с нужным объемом уже сам дополню, мне бы разобраться с алгоритмом по получению вышеописанных переборов.
 
 
   Cyberhawk
 
1 - 08.08.18 - 22:13
Много букв, давай-ка в трех словах
   NSSerg
 
2 - 08.08.18 - 22:16
опять рюкзак.
   barsik123
 
3 - 08.08.18 - 22:21
(1) в трех не получится, и так упростил до переборов.
   barsik123
 
4 - 08.08.18 - 22:28
(2) ну очень похоже на алгоритм рюкзака, нужно распихать товары клиента по пакетам, которые вмещают заданный объем и вес
   Garykom
 
5 - 08.08.18 - 22:50
(0) Характеристики товаров и мест какие?
Только объем или габариты заданы как и для мест?

Все задачки перебора решаются обычными циклами.
   NSSerg
 
6 - 08.08.18 - 23:26
(5) все задачки переборные - как правило перебором «в лоб» не решаются, так как количество наборов равно 2^N при размещении в одном месте, и предел вычислительных возможностей равен где-то 30 предметов, а при размещении в двух местах уже 3^N, и предел равен 20 предметам и т.д.
поэтому либо жадные алггоритмы, либо направленный перебор с отсечениями, либо симплекс-метод и.т.д.
   NSSerg
 
7 - 08.08.18 - 23:33
А если действительно предметов мало, и нужен ненаправленный полный перебор без отсечений - то это рекурсия или вспомогательный массив.

Пусть всего предметов N. Мест для размещения S, разместить надо все предметы.

Процедура перебор(k)
  Если k>N Тогда
     ВывестиНабор();
     возврат;
  КонецЕсли;  
  Для место=1 по S цикл
      РазместитьПредмет(k,S);
      перебор(к+1);
  КонецЦикла;
Конецпроцедуры
Процедура Выполнить()
  перебор(1);
КонецПроцедуры
   NSSerg
 
8 - 08.08.18 - 23:35
Процедура перебор(k)
  Если k>N Тогда
     ВывестиНабор();
     возврат;
  КонецЕсли;  
  Для место=1 по S цикл
      РазместитьПредмет(k,место);// тут была ошибка

      перебор(к+1);
  КонецЦикла;
Конецпроцедуры
Процедура Выполнить()
  перебор(1);
КонецПроцедуры
   NSSerg
 
9 - 08.08.18 - 23:44
Полный семерочный код
перем N,S;
перем предмет[100];
Процедура РазместитьПредмет(k,место)
    Предмет[k]=место;
КонецПроцедуры    
Процедура ВывестиНабор() 
    Для место=1 по S цикл 
        стр=""+место+": ";
        Для k=1 по N цикл
            Если Предмет[k]=место Тогда
                стр=стр+k+" "; 
            КонецЕсли;    
        КонецЦикла;      
        сообщить(стр);
    КонецЦикла;      
    сообщить();
КонецПроцедуры    
Процедура перебор(k)
  Если k>N Тогда
     ВывестиНабор();
     возврат;
  КонецЕсли;  
  Для место=1 по S цикл
      РазместитьПредмет(k,место)// тут была ошибка

      перебор(k+1);
  КонецЦикла;
Конецпроцедуры
Процедура Выполнить() 
    N=4;S=2;
  перебор(1);
КонецПроцедуры
   NSSerg
 
10 - 08.08.18 - 23:45
результат всех возможных размещений четырех предметов в двух местах
1: 1 2 3 4
2:

1: 1 2 3
2: 4
1: 1 2 4 
2: 3 

1: 1 2 
2: 3 4 

1: 1 3 4 
2: 2 

1: 1 3 
2: 2 4 

1: 1 4 
2: 2 3 

1: 1 
2: 2 3 4 

1: 2 3 4 
2: 1 

1: 2 3 
2: 1 4 

1: 2 4 
2: 1 3 

1: 2 
2: 1 3 4 

1: 3 4 
2: 1 2 

1: 3 
2: 1 2 4 

1: 4 
2: 1 2 3 

1:
2: 1 2 3 4
 
 Рекламное место пустует

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует