Girl fan wants to find a boyfriend, but it's for

Late at night, I have nothing to do , Brush my fan group , I saw a female fan writing code so late 、 Change bug, I was immediately moved ：

It seems that she has encountered difficulties in code , I really want to find a boyfriend to help solve it .

So I suddenly made up a topic ：

Female fan you N individual bug Need modification , Yes M A boy , Each boy will revise a part bug. ask ： At least choose a few boys as boyfriends , To repair all bug？（ Make sure that each bug At least one boy will modify ）

After thinking for a long time, I didn't figure out how to do , Then a want to , This can be abstracted into a 「 Set covering problem 」 Do you ？

A collection has N Elements ,M A subset of , ask ： At least a few subsets can cover all elements ？

Baidu search , I was stunned ：

This is actually a NP- Problem completely , That is, there is no polynomial time solution .

The correct solution is to enumerate all the boy subsets , See who can solve all the problems by choosing a boyfriend bug, So the time complexity is

.

Of course, there are approximate solutions ,「 Choose boyfriends one by one 」. Every time from the remaining boys who haven't chosen , Choose the one that can solve the most remaining bug As a boyfriend . All the way to bug It's all solved .

In this way, the problem is perfectly solved ！ Boyfriends line up in order to talk , Pick the one with the greatest advantage every time , After solving your own problems, you can divide . When encountering new problems , Continue to choose the one who can solve the most problems as your boyfriend . Until no new problems arise .

I didn't expect ordinary female fans , There is also a classic in the field of computer theory NP- Problem completely . This also proves the old saying ,「 Science comes from life 」.

Wish this girl bug less and less , The code is getting better , Surpass me as soon as possible .