知识卡片
集合覆盖选择尽量少的子集
集合覆盖先给出待覆盖成员S,以及可供选择的子集族P={A1,…,An};要选出C⊆P,使C中所有子集的并覆盖S,并让所选子集数尽量少。覆盖全部成员是可行条件,选择最少子集是优化目标,两者不能混为一谈。
组建技能团队时,S是必需技能,每名候选人对应他拥有的技能集合Ai,选出的人员对应C。若某项必需技能没有任何候选人具备,就不存在完全覆盖;若能覆盖,也未必已经找到了人数最少的团队。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
集合覆盖是一种优化求解问题,对很多组合数学和资源选择问题给出了漂亮的抽象模型。问题是这样的:给定一个集合S,集合P由集合S的子集A1到An组成,集合C由集合P中的一个或多个子集组成。如果S中的每个成员都包含在C的至少一个子集中则称集合C覆盖集合S。此外,C包含的P的子集应该越少越好。 举个例子,设想
参考来源
- 位置:《算法精解:C语言描述》第7章《Set示例:集合覆盖》(spine1263;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1230.html;u116-ch07-017)。
- 结论依据:116问题定义与技能团队建模两段完整实读,保留给定量、可行性、目标的不同职责,不进行真实人员决策。
- 原始内容:集合覆盖是一种优化求解问题,对很多组合数学和资源选择问题给出了漂亮的抽象模型。问题是这样的:给定一个集合S,集合P由集合S的子集A1到An组成,集合C由集合P中的一个或多个子集组成。如果S中的每个成员都包含在C的至少一个子集中则称集合C覆盖集合S。此外,C包含的P的子集应该越少越好。 举个例子,设想