minizinc - 找到总和为 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-in​​st 必须是 par set 但它是 ``var set of int'

在 MiniZinc 中是否有一种干净/简单的方法来表示这个问题？

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 的初始域是有道理的，而不是完全不同，强制排序将是等效的，但消除了可能解决方案中的一些对称性。