# Maximizing a sequence of items under order and pairwise restriction

Suppose I have a number of items $$\{A ... Z$$} which are ordered accordingly. Each item has an associated weight, for example $$W_A$$. Between all items, there's a criterion $$c$$ which determines whether they fit together. So if $$A$$ and $$B$$ don't fit together, maybe $$A$$ and $$C$$ do, and then the next fitting neighbour from $$C$$ would have to be found.

The goal is to find a chain $$S$$ among these items that has the items in the original order, all subsequent items meet $$c$$ and that maximizes the sum $$\sum_{i \in S} W_i$$. A naive approach would completely explode in runtime I suppose. Does anyone have a way in mind to liken it to a solved problem?

• Try dynamic programming. – Yuval Filmus Jan 18 at 19:57
• Yes I was thinking of the knapsack problem, but it's not quite the same ... – telegott Jan 18 at 20:00
• Do you need every pair in the solution to satisfy $c$, or just adjacent ones? In the former case, this is essentially max clique. – Yuval Filmus Jan 18 at 20:02
• Only between two adjacent elements! Thanks, I'm gonna look into that! – telegott Jan 18 at 20:03