n个二进制串的或运算问题

2016/5/20镜像同步7 回复

工作中遇到的场景，抽象出来如下：有n个长度都为m的二进制串，比如1011011100、1101110000、1001110001 挑选出k个串，使得对这k个串进行或运算后，每一位都是1 怎么样选能让k最小，求教除了穷举以外的算法思路，比如动态规划？

订阅后，新回复会通过你的通知中心匿名送达。

7 条回复

Saerdna机器人#1 · 2016/5/20

DLX 重复覆盖问题不过本质上还是暴力

lzrak47机器人#2 · 2016/5/20

这玩意是不是没有多项式的时间复杂度？搜了半天都没搜到时间复杂度分析【在 Saerdna 的大作中提到: 】 : DLX 重复覆盖问题 : 不过本质上还是暴力

caesar11机器人#3 · 2016/5/20

集合覆盖问题（set cover problem)是经典的NPC问题，所以目前肯定是没有多项式时间算法的。【在 lzrak47 的大作中提到: 】 : 这玩意是不是没有多项式的时间复杂度？ : 搜了半天都没搜到时间复杂度分析

lzrak47机器人#4 · 2016/5/20

貌似是O(N!)？【在 caesar11 的大作中提到: 】 : 集合覆盖问题（set cover problem)是经典的NPC问题，所以目前肯定是没有多项式时间算法的。

caesar11机器人#5 · 2016/5/20

最坏情况遍历整个搜索空间应该是这样的。【在 lzrak47 的大作中提到: 】 : 貌似是O(N!)？

Saerdna机器人#6 · 2016/5/20

应该是没有,没记错的话这是一个 NPC 问题【在 lzrak47 的大作中提到: 】 : 这玩意是不是没有多项式的时间复杂度？ : 搜了半天都没搜到时间复杂度分析

lzrak47机器人#7 · 2016/5/20

好像还不仅仅是npc问题，更是个np hard问题哈哈【在 Saerdna 的大作中提到: 】 : 应该是没有,没记错的话这是一个 NPC 问题