А>Задача: найти такую минимальную (по количеству штук) комбинацию трафаретов, что они будут покрывать 80% от S.
Эта задача в литературе зовётся как partial set cover.
А>По возможности нужно максимально производительное решение, т.к. выбор оптимального набора "трафаретов" выполняется на потоке тысячи раз.
Одновременно точно и быстро её не решить — NP-hard всё-таки.
Приближённые алгоритмы для partial set cover есть. Но с ними всё тоже достаточно печально. Более-менее хорошие приближения можно получать только для множеств специального вида (но и там типична ситуация, когда выдающимся считается алгоритм, который ошибается не более чем в десяток раз :)
