下面是我的问题：
例子：
我们有3天时间来分配产品。公司A的产品：a,a,a,a,a。公司B的产品：b,b,b。公司C的产品：c,c
公平分配： [aab,aabc,abc]
无效分配： [aabc,aabc,ab] 因为第一天有4个产品，第三天有2个产品（差异>1）
无效分配： [abc,aabc,aab] 因为第一天只有一个A产品，第二天有两个A产品，所以A产品的分配不是非递减的。
编辑 如果有一种情况使公平分配变得不可能，请提供简短的描述，我会接受答案。
Gareth Rees对djna的回答进行的评论是正确的 - 以下反例是无解的:
我使用了下面这个最简单的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() - 它们只是做你所期望的事情。）因为我认为这个问题很有趣，所以我使用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都非常朴素，并且具有大量的分解。为了解决更大的实例，可能应该用更智能的变体来替换它们（例如，使用正则约束）。
已经证明，点4和点5不兼容：
|C(i) - C(j)| <= 1因此，您需要放宽其中一个约束条件。老实说，虽然我能感受到为什么要设置4（为了避免无限期延迟一个公司的分配），但我认为可以用其他方式表达，以考虑分配的第一天和最后一天是特殊的（因为在第一天，您通常会拿走前一个公司剩下的东西，在最后一天，您会分配剩下的东西）。
点3确实强制连续性。
数学上：
对于任何有产品的公司A，存在两天i和j，使得：
可以承认，这个问题变得非常容易解决了 :)
我认为你不能总是满足你的要求。
考虑4天，从供应商A购买6件物品和从供应商B购买6件物品。