6

这是我的问题：

  • 有 n 家公司分销产品。
  • 所有产品应在k天内分发
  • Ci公司的产品分配应该是连续的-这意味着它可以在第2,3,4,5天分发，但不能在2,3,6,7天分发
  • Ci 在第 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] 因为第 1 天有一个产品 A，第 2 天有 2 个产品 A，所以产品 A 的分配不是非递减的

编辑 如果存在无法进行公平分配的情况，请提供简短描述，我会接受答案

4

4 回答 4

3

Gareth Rees 对 djna 答案的评论是正确的——以下反例无法解决：

  • 3天，A公司7件，B公司5件

我使用以下最愚蠢的蛮力 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()了——它们只是按照您的期望进行。）

于 2010-11-09T12:46:01.340 回答
2

因为我认为这个问题很有趣，所以我做了一个模型来使用MiniZinc寻找解决方案。使用Gecode后端，初始示例显示在大约 1.6 毫秒内有 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都非常幼稚，并且分解很大。要解决更大的实例，可能应该用更智能的变体替换它们（例如通过使用常规约束）。

于 2010-11-10T14:01:15.653 回答
1

事实证明，第 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，存在两天 i 和 j，这样：

  • C(i,A) > 0 和 C(j,A) > 0
  • 对于任何一天 x 使得 x < i 或 x > j，C(x,A) = 0
  • 对于任何一天 x 使得 i < x < j, C(x,A) = C(x)

诚然，问题变得微不足道:)

于 2010-11-09T13:48:18.637 回答
0

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

考虑 4 天，供应商 A 的 6 件商品和供应商 B 的 6 件商品。

于 2010-11-09T11:15:55.160 回答