求助一题

回复帖子

@soul_maker 2020-05-24 11:23 回复

有$n$个长度为$n$的$01$串,从中选出尽可能少的串,使得每位上保证至少有一个$1$,求最小选择串数?

如:

$n=3$,分别为:

$110\ 100\ 001$

那么选择$1,3$串可以保证每个位置上都有$1$。最少选$2$个

@OIforJoy 2020-05-24 11:31 回复 举报

这是SCP,经典的NP-Complete...状压DP过不去就试试启发式搜索吧...

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。