algorithm - 覆盖目标的传感器的最小成本子集

Question

我在动态规划中有一个问题，如果我有一组覆盖目标的传感器(一个目标可能被多个传感器覆盖)，我如何找到传感器的最小成本子集，知道每个传感器都有自己的成本？我想了很多关于这个，但我无法到达递归论坛来编写我的程序？贪婪算法有时会给我错误的最小成本子集，我的问题是传感器在覆盖目标时重叠，有什么帮助吗？

例如:我有一组成本/重量 = {s1:1,s2:2.5,s3:2} 的传感器，我有三个目标 = {t1,t2,t3}。传感器覆盖范围如下:={s1:t1 t2,s2:t1 t2 t3,s3:t2 t3} 我需要通过动态规划获得最小成本子集，对于上面的例子，如果我使用贪心算法我会得到 s1,s3 但是正确答案只有 s2

Answer 1

检查第 3 部分，它标记了MWCDC的动态规划算法

https://docs.google.com/viewer?a=v&q=cache:5vPrmVg7jDMJ:www.cs.iit.edu/~wan/Journal/tcs10.pdf+&hl=en&gl=us&pid=bl&srcid=ADGEESglfvp6XtFIkqDZZ-E-Tun4AWPTZV_V7z32pTvJ05K6tdkCoefpsAxPxdK44jYDvPNLDEwYI8uK-PMlLGthsaV8-ow63utalgWPnyLrUUBKhoTTVuYwUiKSHlCXU-HXKHVeHvh4&sig=AHIEtbQGka8F39MaT8yAy4G9Kvv8TPsvJA