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

Опасность H5 обнаруживают только датчики A, D и G. Поэтому необходимо выбрать как минимум два из них. Самая дешёвая пара — A и D: их общая стоимость равна 4 + 4 = 8.

После выбора A и D покрытия имеют вид: H1 — 1 раз, H2 — 2 раза, H3 — 0 раз, H4 — 1 раз, H5 — 2 раза.

Чтобы дополнительно закрыть H1, H3 и H4 минимум дважды, выбираем B и C:

• B обнаруживает H1 и H3;
• C обнаруживает H3 и H4.

Теперь каждая опасность обнаруживается минимум двумя датчиками:

• H1: A, B;
• H2: A, D;
• H3: B, C;
• H4: C, D;
• H5: A, D.

Стоимость набора: 4 + 2 + 1 + 4 = 11.

Ответ: A, B, C, D; минимальная стоимость — 11.