• 
• 题库
• 比赛
• 问吧
• 讨论
• 状态

讨论 / 子集覆盖问题

• 发布新讨论
• 跳转至 讨论列表

curimit 2009-07-13 08:13:00

点我顶贴 收藏 删除

子集覆盖问题

给出一些子集，要求选取最少的子集把全集覆盖

谁能在1秒之内解决任意n=300规模的数据？？？！！！

#1 wish@2009-07-12 20:11:00

12337 回复 删除

这貌似不是 NPC 么....LZ 会?

#2 wish@2009-07-12 20:15:00

12338 回复 删除

如果有兴趣可以看下精确覆盖问题的

X 算法(Algorithm X)

Knuth 发明的一种算法,wikipedia 上有

#3 curimit@2009-07-13 08:13:00

12344 回复 删除

不是exact cover问题。。。

就是子集覆盖问题，因为听说这个问题优化一下可以解决非常大的规模。

查看更多回复

拥有 RQNOJ 账号，您可以：

• 查看海量题库，并提交您的代码
• 参加比赛，证明实力
• 与大家讨论，解答疑问，分享心得

注册

已有账号？

登录

提交回复

  快速帮助 | 运行状态 | 反馈举报 | 关于我们 | 免责声明 | 浙ICP备11060257号

    Processed in 0.0038	Second(s)
    Copyright (C) RQNOJ 2007-2019. All Rights Reserved.