但我们会发现，随着子集集合个数的增长，总的组合种数是以指数级的增长。如果某鱼上有100个商家，那么就会有2的100次方这么多种组合，有生之年根本不可能穷举完。所以集合覆盖问题无法在有限时间内求出最优解。

这时候我们就要选择一些近似算法，比如我在网上找到的不带权重的贪婪算法：
1、令C=空；
2、WhileC不等于E
do
{
找Si属于S，使得C和Si的并集最大；
C=C和Si的并集；
}
3、输出Si的集合；

带权重的贪婪算法：
1、令C=空；
2、WhileC不等于E
do
{
找成本效益最小的集合Si，令a=Wi/(|Si-C|)，即成本效益；
选取Si，并对每个每个元素E属于Si-C，规定成本效益；
C=C和Si的并集；
}
3、输出Si的集合；

这个算法的核心在于哪一个集合优先选择。这里的思路就是，首先选择性价比高的，比如花10块钱，有个商家卖1张卡，有的商家卖2张卡，那优先选择卖2张卡的，因为后者的性价比高。

楼主还能想到另一种选择的方法，就是把每个商家的货源列成表格，就可以推出每个元素的稀有度，我们把每个元素按照稀有度打分，比如很稀有的打100分，烂大街的打1分，然后计算每个集合的总分，再除以价格，就是性价比，按照从大到小排列，以这个顺序作为选择的顺序，其实是一种算法的优化。

其他算法我们就不展开介绍了，有兴趣可以自己深入研究。穷举是确定型算法，但是时间复杂度大；贪心算法是非确定性算法，可以找到近似解，但不是最优解。

最后我们来回顾一下无角标神话再临。
输入：
E={33张无角标的神话再临卡牌}
S1={《桃园结义》的无角标神话再临武将}，W=40
S2={《卧龙传》的无角标神话再临武将}，W=20
S3={《凤雏传》的无角标神话再临武将}，W=20
S4={《曹操传》的无角标神话再临武将}，W=10
S5={《貂蝉传》的无角标神话再临武将}，W=20
S6={《虎牢激战》的无角标神话再临武将}，W=40
S7={《官渡之战》的无角标神话再临武将}，W=30
S8={《火烧赤壁》的无角标神话再临武将}，W=20
S9={《火烧连营》的无角标神话再临武将}，W=10
S10={《乱世诸神》的无角标神话再临武将}，W=40
这里W是指平均的近似价格
输出：
C={S2,S3,S4,S5,S7,S9,S10}，W总=150
也就是说差不多150元就能玩遍无角标神话再临武将了，哎，穷人的快乐就是这么随意，且充实！

参考文献
https://www.jianshu.com/p/21f0a75d73e1 集合覆盖问题（Set Cover Problem）和点覆盖问题及归约
https://wenku.baidu.com/view/3523a3caa1c7aa00b52acb67.html 带权集合覆盖的一种近似算法
https://wenku.baidu.com/view/dd471e553c1ec5da50e27055.html 组合优化——集合覆盖问题

第二部分 完

最后一部分，我们来补一下最开始提到的，被排除的官盗的图片，细心的你会发现，这其实是一篇官盗系列的总结贴。
S2《一战成名》

S2《血战到底》

S2《铁血双雄》
武将牌同上

S4《倾国美人》

S5《群雄逐鹿》

谢谢你们看到了最后，本文写了很长时间，还请不要盗图，转载请注明出处。
最后致那些哗众取宠、到处盗图嘚瑟的人，你们和楼主的差距除了钱，还有对收藏的热爱，对知识的敬畏之心。
2020年4月24日