Каждая из опасностей H1–H5 должна покрываться минимум двумя выбранными датчиками. Найдите набор минимальной стоимости. Датчик A обнаруживает H1, H3, H5 и стоит 3; B — H2, H4, H5 и стоит 2; C — H1, H2 и стоит 5; D — H3, H4 и стоит 2; E — H2, H3, H5 и стоит 1; F — H1, H4 и стоит 4; G — H3, H4 и стоит 2.

Выберем датчики A, B, E, F.

1. H1: датчики A и F — 2 покрытия.
2. H2: датчики B и E — 2 покрытия.
3. H3: датчики A и E — 2 покрытия.
4. H4: датчики B и F — 2 покрытия.
5. H5: датчики A, B и E — 3 покрытия.

Стоимость набора: \(3+2+1+4=10\).

Меньший набор невозможен: для опасности H1 нужны как минимум два датчика из A, C, F, а для H4 — как минимум два из B, D, F. Дополнительно необходимо обеспечить второе покрытие H2 и H5. Минимальный подходящий набор состоит из четырёх датчиков, и набор A, B, E, F имеет наименьшую стоимость.

Ответ: A, B, E, F; минимальная стоимость — 10.