精确覆盖 DLX

问题描述:

  给出全集S,  和n个S的子集C[0 to n-1],  找出 k(0 < k < n)个子集, 使能够覆盖S, 且每个元素只覆盖一次。 

思路:

  1. 暴力搜索: 找出2^k个子集组合, 判断是否满足条件。 优化: 回溯。

  2. 另一种搜索:找出能够覆盖S中第1个元素的子集C[i],删除与C[i]有交集的子集, 删除S中C[i]能覆盖的元素得到S_new,

     对S_new执行相同的操作, 如果没有成功则回溯选择另一个能够覆盖S中的第1个元素的子集C[j]. 直到S_new为空。

    对于这种搜索用dancing links结构。 

原文地址:https://www.cnblogs.com/ddmiao/p/3656789.html