# Minimum cost subset of sensors covering targets

I have a dynamic programming problem:

If I have a set of sensors covering targets (a target might be covered by mutiple sensors) how can I find the minimum cost subset of sensors covering all targets given each sensor has a cost?

I have thought a lot about this, but I can't reach the recursive formula to write my program. The greedy algorithm does not always provide the correct minimum cost subset. My problem is that sensors overlap in covering targets. Any help?

Example: I have set of sensors $\{s_1,s_2,s_3\}$ with costs $\{1,\frac{5}{2},2\}$ and 3 targets $\{t_1,t_2,t_3\}$. Sensors cover $\{t_1 t_2,t_1 t_2 t_3,t_2 t_3\}$ and I need to get minimum cost subset by dynamic programming. For the above example if I use greedy algorithm I would get $s_1,s_3$ but the right answer is $s_2$ only.

Your problem is equivalent to the weighted version of Set Cover, which is NP-complete (and delving into other complexity classifications, W-complete and inapproximable within $O(\log n)$).