博览会产品分发算法

Question

这里是我的问题：

• 有n个企业分布 产品。
• 所有产品应分布在K天
• 分发公司的产品词应该是连续的 - 这意味着它可以在几天2,3,4,5被分配但不2,3,6,7
• 数在日期J分布式产品由公司次的应小于（或等于）在日期J-1（如果有任何在日期J-1）天之间分布的产品之间
• 差i和j不应该大于1

实施例：

我们有3天的时间来分销产品。 A公司的产品：a，a，a，a，a。 B公司的产品：b，b，b。 C公司的产品有：C，C

公平分配： [AAB，AABC，ABC]

无效分布： [AABC，AABC，AB] 因为第1天有4产品，在第3天2个产品（差值> 1）

无效分布： [ABC，AABC，AAB] 因为第一天有一个产品A，并在第2天有2个产品A，因此产品A的分布并不非递减

编辑 如果存在使得公平分配是不可能的，请为它提供简短的说明的情况下，我会接受的答案

Answer 1

加雷思·里斯对DJNA的答复意见是正确的 - 以下反是无法解决：

• 3天，来自A公司的7个项目和来自B公司的5个项目

我用以下dumbest可能的蛮力Perl程序测试了它（这需要一秒钟尽管是非常低效）：

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"; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

请看看，并验证我还没有做出任何愚蠢的错误。 （为了简洁起见，我省略了max()和min() - 他们只是做你期望的。）

Answer 2

我不不要以为你总能满足你的要求。

考虑4天，并从供应商A 6项，并从供应商B. 6项

Answer 3

已经显示的是，点4和5不匹配：

• 4：对于任何日期J，对于任何公司A，C（J，A）== 0或C（J， A）> = C（J + 1，A）
• 5：对于任何天i和j，|C(i) - C(j)| <= 1

您从而需要放松或者约束。老实说，当我感觉到为什么4已经到位（为了避免延迟一个公司的无限期分配），我认为可以表达其他方式来考虑分配的第一天和最后一天是特殊的（从第一天起，你通常会拿走前一家公司留下的内容，并在最后一天分发剩下的内容）。

点3确实强制邻接。

数学：

对于任何公司A，其具有的产品，存在2天i和j，使得：

• C（I，A）> 0和C（J，A） > 0
• 任何天x，使得x < i或X>Ĵ，C（X，A）= 0
• 任何天x使得i < X <Ĵ，C（X，A）= C （x）

诚然，这个问题就变成了微不足道的解决:)

Answer 4

因为我觉得这个问题很有趣，我没有使用MiniZinc寻找解决方案的典范。通过Gecode后端，初始示例显示在大约1.6 ms内有20个解决方案。

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; 

谓词decreasing_except_0和consecutive都非常懂事，有较大的分解。要解决更大的实例，可能需要用更智能的变体来替换它们（例如使用常规约束）。