Имя: Пароль:
1C
1С v8
Разбиение товаров по грузовым местам, помогите с алгоритмом
0 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)

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

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

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

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