# Picking the most cost efficient sets

I have two 2D arrays: $$P[n][s]$$ and $$C[n][s]$$, $$s \leq n$$.

P contains sets of nodes and $$C$$ the cost of a set in $$P$$, e.g. the cost of $$P[2][2]$$ is $$C[2][2]$$ and a set $$p \in P = \{ s_0, s_1, ..., s_{n-1} \}^q, q \leq n$$, e.g. $$p=\{s_0, s_3\}$$.

For every row I can pick at most one set but in the end the union of the picked sets needs to contain all nodes $$\{s_0, s_1, ..., s_{n-1} \}$$.

How do I find the least expensive picks in linear time?

If you are able to find the least expensive picks in linear (or even polynomial) time then $$P=NP$$.
Your problem is a generalization of the set-cover problem: given a set $$X$$ of items and a collection $$S = \{S_1, \dots, S_m \} \subseteq 2^X$$ of subsets of $$X$$, find $$S' \subseteq S$$ such that $$\cup_{S_i \in S'} S_i = X$$ and $$|S'|$$ is minimized.
This is exactly your problem once you set $$n=|X|$$, $$s=1$$, $$P[i][1] = S_i$$, and $$C[i][1]=1$$.