这个问题来源于现实生活，但我把它转化为更通用的“教科书式”表述。我怀疑它是NP问题，但我特别想知道它是否有一个名称或者是否众所周知，因为我认为我不可能是第一个遇到它的人。;-)
假设有N个客人参加聚餐派对。每个客人可以带来自己的“招牌菜”，也可以什么都不带。每个客人都喜欢或讨厌其他客人可能带来的菜肴（因为他们都是老朋友，这一点是事先已知的！），但他们都喜欢自己的菜肴。
是否存在一种确定性算法，不需要指数时间来找到满足约束条件的最小菜肴集，以便所有客人都能找到至少一道自己喜欢的菜肴？我说“最小的” ，但实际上可能会有多个解决方案，如果可能的话，我想知道它们全部是什么。
或者，更抽象地说，想象一个正方形矩阵，其中所有元素都是0或1，并且所有对角线元素都是1。哪些行的最小集合使得每个集合中行的和（或二进制OR）没有零？（行代表菜肴，列代表客人，1表示一个客人喜欢一道菜，由于每个人都喜欢自己的菜，因此对角线元素为1。）
这可以推广到非正方形矩阵，或者通过删除对角线=1规则来推广（尽管后者保证始终至少有一个解）。但是我现在不关心那些情况...
我已经有一个通过穷举搜索解决它并足够快的程序，适用于N约为20左右，但它需要指数时间。我想我可能需要求助于随机算法，以找到更大N值的足够好的解决方案。
添加
哇，谢谢你的快速回答！“集合覆盖”，这就是我正在寻找的名称。:)