找到总和为 n 的最小全差数组

Question

这看起来是个简单的问题，但我在 MiniZinc 中找不到简单的方法来表示它。

include "globals.mzn";

int: target;
int: max_length;

var 1..max_length: length;

array[1..length] of int: t;

constraint sum(t) = target;
constraint alldifferent(t);

solve minimize length;

此程序错误： MiniZinc: type error: type-inst must be par set but is ``var set of int'

在 MiniZinc 中是否有 clean/simple 方法来表示这个问题？

Answer 1

MiniZinc 中的数组具有固定大小。因此编译器说 array[1..length] of int: t 是不允许的，因为 length 是一个变量。

MiniZinc 提供的替代方案是具有可选类型的数组，这些是可能存在的值。这意味着当你写[t | t in 1..length]这样的东西时，它实际上会给你一个1..maxlength的数组，但是有些元素可以标记为absent/<>.

对于这个特殊问题，您还忽略了 t 本身应该是一个变量数组这一事实。 t 的值在编译时还未知。因此，表述此问题的更好方法是允许 t 的值在超出所选长度时为 0：

include "globals.mzn";

int: target;
int: max_length;

var 1..max_length: length;

array[1..max_length] of var int: t;

constraint sum(t) = target;
constraint alldifferent_except_0(t);
constraint forall(i in length+1..max_length) (t[i] = 0);

solve minimize length;

改进模型的下一步是确保 t 的初始域有意义，而不是完全不同，强制排序是等效的，但消除了可能解决方案中的一些对称性.

找到总和为 n 的最小全差数组

Find the smallest alldifferent array whose sum is n

minizinc