Feria algoritmo de distribución de productos

Question

Aquí está mi problema:

• hay n empresas distribuidoras productos.
• Todos los productos deben ser distribuidos en k días
• La distribución de productos de la empresa CI debe ser consecutivos - que significa que puede ser distribuida en los días 2,3,4,5 2,3,6,7 pero no
• número de productos distribuidos por la empresa Ci el día j debe ser menor que (o igual) el día j-1 (si hubo alguno en el día j-1)
• la diferencia entre productos distribuidos entre los días i y j no debe mayor que 1

Ejemplo:

Tenemos 3 días para distribuir productos. Productos de la compañía A: a, a, a, a, a. Productos de la empresa B: b, b, b. Productos de la empresa C: C, C

distribución justa: [AAB, aabc, abc]

distribución no válido: [aabc, aabc, ab] porque en el 1er día hay 4 productos, el 3 días 2 productos (diferencia> 1)

distribución no válido: [abc, aabc, aab] porque en el 1er día hay un producto a, y el segundo día hay 2 productos A, no tan distribución de producto A es no decreciente

EDITAR si hay un caso que hace imposible una distribución justa por favor provea con una descripción breve, voy a aceptar la respuesta

Answer 1

comentario de Gareth Rees sobre la respuesta de djna es correcto - el siguiente contraejemplo es irresoluble:

• 3 días, 7 artículos de la empresa A y 5 artículos de la empresa B

Probé esto con el siguiente programa Perl de fuerza bruta, el más tonto posible (que tarda mucho menos de un segundo) , A pesar de ser muy ineficiente):

my ($na, $nb) = (7, 5); 
for (my $a1 = 0; $a1 <= $na; ++$a1) { 
    for (my $a2 = 0; $a2 <= $na - $a1; ++$a2) { 
     my $a3 = $na - $a1 - $a2; 
     for (my $b1 = 0; $b1 <= $nb; ++$b1) { 
      for (my $b2 = 0; $b2 <= $nb - $b1; ++$b2) { 
       my $b3 = $nb - $b1 - $b2; 
       if ($a1 >= $a2 && $a2 >= $a3 || $a1 == 0 && $a2 >= $a3 || $a1 == 0 && $a2 == 0) { 
        if ($b1 >= $b2 && $b2 >= $b3 || $b1 == 0 && $b2 >= $b3 || $b1 == 0 && $b2 == 0) { 
         if (max($a1 + $b1, $a2 + $b2, $a3 + $b3) - min($a1 + $b1, $a2 + $b2, $a3 + $b3) <= 1) { 
          print "Success! ($a1,$a2,$a3), ($b1,$b2,$b3)\n"; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Por favor, echar un vistazo y comprobar que no he cometido errores estúpidos. (He omitido max() y min() por brevedad; solo hacen lo que cabría esperar.)

Answer 2

I don' Creo que siempre puedes cumplir tus requisitos.

Considere 4 días y 6 artículos de proveedor A y 6 artículos de proveedor B.

Answer 3

Se ha demostrado que los puntos 4 y 5 eran incompatibles:

• 4: Para cualquier día j, para cualquier empresa A, C (j, A) == 0 o C (j, A)> = C (j + 1, A)
• 5: Para cualquier día i y j, |C(i) - C(j)| <= 1

lo tanto es necesario relajante ya sea restricción. Honestamente, mientras tengo una idea de por qué 4 se puso en marcha (para evitar retrasar indefinidamente la distribución de una empresa), creo que podría expresarse de otro modo para considerar el primer y el último día de distribución como especiales (ya que el primer día , normalmente toma lo que dejó la empresa anterior y el último día distribuye lo que queda).

El punto 3 fuerza la contigüidad.

Matemáticamente:

Para cualquier empresa A, que tiene productos, existen dos días i y j tal que:

• C (i, A)> 0 y C (j, A) > 0
• para cualquier día x tal que x < i o x> j, C (x, a) = 0
• para cualquier día x tal que i < x < j, C (x, a) = C (x)

Es cierto que el problema entonces se convierte en trivial para resolver :)

Answer 4

Desde pensé que el problema era divertido, hice un modelo para la búsqueda de soluciones utilizando MiniZinc. Con el backend Gecode, se muestra que el ejemplo inicial tiene 20 soluciones en aproximadamente 1,6 ms.

include "globals.mzn"; 

%%% Data 
% Number of companies 
int: n = 3; 
% Number of products per company 
array[1..n] of int: np = [5, 3, 2]; 
% Number of days 
int: k = 3; 

%%% Computed values 
% Total number of products 
int: totalnp = sum(np); 
% Offsets into products array to get single companys products 
% (shifted cumulative sum). 
array[1..n] of int: offset = [sum([np[j] | j in 1..i-1]) 
          | i in 1..n]; 

%%% Predicates 
predicate fair(array[int] of var int: x) = 
     let { var int: low, 
      var int: high 
     } in 
     minimum(low, x) /\ 
     maximum(high, x) /\ 
     high-low <= 1; 
predicate decreasing_except_0(array[int] of var int: x) = 
     forall(i in 1..length(x)-1) (
       (x[i] == 0) \/ 
       (x[i] >= x[i+1]) 
     ); 
predicate consecutive(array[int] of var int: x) = 
     forall(i in 1..length(x)-1) (
      (x[i] == x[i+1]) \/ 
      (x[i] == x[i+1]-1) 
     ); 

%%% Variables 
% Day of production for all products from all companies 
array[1..totalnp] of var 1..k: products 
      :: is_output; 
% total number of products per day 
array[1..k] of var 1..totalnp: productsperday 
     :: is_output; 

%%% Constraints 
constraint global_cardinality(products, productsperday); 
constraint fair(productsperday); 
constraint 
    forall(i in 1..n) (
     let { 
      % Products produced by company i 
      array[1..np[i]] of var int: pi 
       = [products[j] | 
       j in 1+offset[i]..1+offset[i]+np[i]-1], 
      % Products per day by company i 
      array[1..k] of var 0..np[i]: ppdi 
     } in 
      consecutive(pi) /\ 
      global_cardinality(pi, ppdi) /\ 
      decreasing_except_0(ppdi) 
    ); 

%%% Find a solution, default search strategy 
solve satisfy; 

Los predicados decreasing_except_0 y consecutive son a la vez muy ingenuo, y tienen grandes descomposiciones. Para resolver casos más grandes, probablemente uno debería reemplazarlos por variantes más inteligentes (por ejemplo, usando la restricción regular).