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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.