Algorithms to solve the "set covering problem"

Consider having M keys and N locks. Every key opens one or more locks: | lock1 lock2 lock3 lock4 -----+------------------------ key1 | x x key2 | x x key3 | x x x key4 | x x key5 | x x Given an arbitrary set of locks you have to open (e.g. 2,3,4), the task is to find a minimal set of keys to accomplish this. In the example above, the set [key4, key5] fulfils that condition. The underlying problem is called "set covering problem" and the corresponding decision problem is NP-complete.

There is no official package available for openSUSE Leap 15.3


openSUSE Tumbleweed