时间戳

首页 > 解决方案 > 找到总和为 n 的最小的 alldifferent 数组

minizinc - 找到总和为 n 的最小的 alldifferent 数组

问题描述

这似乎是一个如此简单的问题，但我无法在 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 中是否有一种干净/简单的方法来表示这个问题？

标签： minizinc

解决方案

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

推荐阅读