# 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: 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