= Weighted-Sequence Problem =

== Problem Description ==
In the weighted-sequence problem we are given a set of leaves (nodes) and an
integer m — maximum cost. Each leaf is a pair (weight, cardinality) where
weight and cardinality are integers. Every sequence (permutation) of leaves is
such that all leaves but the first are assigned a color. A colored sequence is
associated with the cost. The task is to find a colored sequence with the cost at
most m.

For a set S of leaves and an integer m, we denote the corresponding weighted-
sequence problem by [S, m]. We say that an integer m is optimal with respect
to a set S of leaves if m is the least integer u such that the weighted-sequence
problem [S, u] has a solution.

Let M be a sequence of n leaves l_0, ..., l_{n−1}. For each leaf l_i , 0 ≤ i ≤ n − 1,
by w(l_i) and c(l_i) we denote its weight and cardinality, respectively. We color
each leaf l_i , 1 ≤ i ≤ n − 1, green, red, or blue; the leaf l_0 is not colored.
We define the costs of leaves as follows. For the leaf l_0, we set
cost(l_0) = w(l_0).

For every colored leaf l_i , 1 ≤ i ≤ n − 1, we set

                 w(l_i) + c(l_i)          if l_i is green
    cost(l_i) =  cost(l_{i−1}) + w(l_i)   if l_i is red   
                 cost(l_{i−1}) + c(l_i)   if l_i is blue

The cost of the sequence M is the sum of the costs of its colored leaves:
cost(M ) = cost(l_1) + ... + cost(l_{n−1}).

== Predicates ==

 * '''Input''': {{{leafWeightCardinality/3, num/1, max_total_weight/1, innerNode/1}}}

 * '''Output''': {{{posColor/2, leafPos/2}}}

== Input format ==
An input consists of the following parts: 

 * n leaves are given with corresponding weight and cardinality (there are 1..n leaves):
   {{{leafWeightCardinality(leaf1,w1,c1). ... leafWeightCardinality(leafn,wn,cn).}}} 
   where w1..wn, c1..cn are integers.

 * The number of leaves in the tree is given by {{{num(n).}}} 

 * Integer mv is given by  {{{max_total_weight(mv).}}}

 * n-1 inner nodes are given: {{{innerNode(1). ... innerNode(n-1).}}}


== Output format ==

A solution is represented by means of a constant "exists" if there is
a tree T and a specification of T in the following format

 {{{posColor(1,color) ... posColor(n,color)}}}

 {{{leafPos(1,pos) ... leafPos(n,pos)}}}
 where pos is a location in the sequence


== Example(s) ==

Given the input:
{{{
leafWeightCardinality(1,45,44). leafWeightCardinality(2,21,3). leafWeightCardinality(3,64,74). leafWeightCardinality(4,29,91). leafWeightCardinality(5,80,48). leafWeightCardinality(6,91,8).
leafWeightCardinality(7,10,64). leafWeightCardinality(8,62,79).

innerNode(1). innerNode(2). innerNode(3). innerNode(4).
innerNode(5). innerNode(6). innerNode(7).

num(8). max_total_weight(495).
}}}

The output of the solver should look like: 
{{{
leafPos(1,7). leafPos(2,4). leafPos(3,6). leafPos(4,5). leafPos(5,2).
leafPos(6,1). leafPos(7,0). leafPos(8,3). 

posColor(7,green). posColor(6,red). posColor(5,red). posColor(4,green). 
posColor(3,red). posColor(2,blue). posColor(1,blue). 

}}}

Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/weighted_sequence-sample.zip|download]]


== Problem Peculiarities ==

'''Type''': Search
'''Competition''': Both


== Notes and Updates ==



== Author(s) ==
 * Authors: Marcello Balduccini, Yuliya Lierlier, Shaden Smith 	
  * Affiliation: Kodak Research Labs and University of Kentucky