Найдите наименьший из всех различных массивов, сумма которых равна n

Question

Это кажется такой простой проблемой, но я не могу найти простой способ представить это в MiniZin c.

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'

Есть ли чистый / простой способ представить эту проблему в MiniZin c?

Answer 1

Массивы в MiniZin c имеют фиксированный размер. Поэтому компилятор говорит, что array[1..length] of int: t недопустимо, потому что length - это переменная.

Альтернатива, которую предлагает MiniZin c, - это массивы с типами optional , это значения это могло существовать. Это означает, что когда вы напишете что-то вроде [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 имеет смысл, и вместо того, чтобы быть разными, принудительное упорядочение было бы эквивалентно, но устраните некоторую симметрию в возможных решениях.