h**6 发帖数: 4160 | 1 已经一个n*m的0/1矩阵,行数n>>列数m,求最少需要取多少行,才能保证每列至少有1
个1。 |
l*****a 发帖数: 14598 | 2 不缺条件吗?
至少你要保证有一个解把
1
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 已经一个n*m的0/1矩阵,行数n>>列数m,求最少需要取多少行,才能保证每列至少有1 : 个1。
|
a********m 发帖数: 15480 | 3 上dp。
1
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 已经一个n*m的0/1矩阵,行数n>>列数m,求最少需要取多少行,才能保证每列至少有1 : 个1。
|
u***n 发帖数: 117 | 4 没看出难点诶,先找出每列的第一个1所在行,然后求这些行号的最大值。 |
h**6 发帖数: 4160 | 5 不是一定从第一行起连续选取,可以从矩阵中任意取若干行。 |
m*****n 发帖数: 2152 | 6 楼主把题目变形了吧,这是那道国旗颜色的题。
而且为什么要用矩阵,用bitset不是更快吗。
刚想了一下,可以用bfs,但可能不是最好的。
1
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 已经一个n*m的0/1矩阵,行数n>>列数m,求最少需要取多少行,才能保证每列至少有1 : 个1。
|
r****t 发帖数: 10904 | 7 没看懂,不是最少取m行就行了么? 取 m-1 行不可能满足,m+1 行又比 m 多。
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是一定从第一行起连续选取,可以从矩阵中任意取若干行。
|
h**6 发帖数: 4160 | 8 看来我的表达能力堪忧,很多人都没理解题意。
比如矩阵
0 1 0 0 1
0 0 0 1 1
1 0 1 0 1
1 0 0 1 0
1 1 0 1 0
0 0 1 1 0
答案是2,取第3行和第5行就能保证每列至少有一个1。 |
x***y 发帖数: 633 | 9 Backtracking with cutting branches that cannot be optimal; A good start is
to have the columns sorted by how many 1s they have; and then start from the
column with the smallest number. |
l*********8 发帖数: 4642 | 10 m的范围是多大?
1
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 已经一个n*m的0/1矩阵,行数n>>列数m,求最少需要取多少行,才能保证每列至少有1 : 个1。
|
|
|
l*********8 发帖数: 4642 | 11 想了一个算法, O(logM * K^2) time, where K=min(2^M, N) |
b*********n 发帖数: 464 | 12 好像是NP问题http://en.wikipedia.org/wiki/Set_cover_problem
现在能想到的只有backtrack。可以通过下面的方法缩小搜索空间:
1.可以先用geedy得到一个次优解:首先用含有1最多的行,然后一次选取能增加1最多
的行,直到m个1被cover。假设次优解是m1(m1<=m).backtrack最多需要搜索m1层。
2.如果一行被另一行cover,删除这一行。如果有多行相等,只保留一行。
3.如果某一列只有被一行包括,选定这一行,这个在回溯之前做
1
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 已经一个n*m的0/1矩阵,行数n>>列数m,求最少需要取多少行,才能保证每列至少有1 : 个1。
|
h*******e 发帖数: 1377 | |
M*******a 发帖数: 1633 | 14 应该NP,相当于set covering problem,每一行cover列的subset,怎么样找最小的行
集合来cover所有的列
所以NP
NP要找最优解基本只能bracktracking。 |
s*****r 发帖数: 108 | 15 楼上那些说 NP 的其实都是说 NPC 请弄清楚 |
l***i 发帖数: 1309 | 16 dp[r][mask] is the number of rows from row[0..r-1], that is, the first r
rows to cover bits in mask
dp[0][0] = 0
dp[0][mask] = INF for mask != 0
for r = 1 to n
for b = 0 to (1<
{
b2 = b | matrix[r-1]; // interpret row[r-1] as an integer, this will
only work if m is 64 or less
dp[r][b2] = min(dp[r-1][b2], dp[r-1][b] + 1); // either not use row[r-1
] or use row[r-1]
}
return dp[n][(1<
more bookkeeping |