% Prize collecting problem.
%
int: n; % size
array[1..n,  0..n] of int: p;

array[1..n] of var 0..n: next;% next posn in tour : 
                              % 1 for last edge, 0 for unused

array[1..n] of var 0..n: pos; % posn of node i in path, 0 = notin

constraint pos[1] = 1;

constraint forall(i in 1..n) (
  ( pos[i] > 0 <-> next[i] > 0 ) /\
  (next[i] > 1 -> pos[i]+1 = pos[next[i]])
);

constraint all_different_except_0(next);

predicate all_different_except_0(array[int] of var int: x) =
  forall(i in index_set(x)) (
    x[i] = 0 \/ forall(j in index_set(x) where j > i)(x[i] != x[j])
  );
solve 
  :: seq_search([
    int_search(next, largest, indomain_max, complete),
    int_search(pos, largest, indomain_max, complete)])
  maximize sum(i in 1..n)(p[i, next[i]]);

output 
  [ "next =" ++ show(next) ++ "\n", 
    "pos =" ++ show(pos) ++ "\n",
    "obj =" ++ show(sum(i in 1..n)(p[i, next[i]])) ++ "\n"
  ];