Picking the most cost efficient sets
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$.