h**6
发帖数: 4160 | 1 已经一个n*m的0/1矩阵，行数n>>列数m，求最少需要取多少行，才能保证每列至少有1
个1。 |
l*****a
发帖数: 14598 | 2 不缺条件吗？
至少你要保证有一个解把
1
【在 h**6 的大作中提到】
: 已经一个n*m的0/1矩阵，行数n>>列数m，求最少需要取多少行，才能保证每列至少有1
: 个1。
|
a********m
发帖数: 15480 | 3 上dp。
1
【在 h**6 的大作中提到】
: 已经一个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 的大作中提到】
: 已经一个n*m的0/1矩阵，行数n>>列数m，求最少需要取多少行，才能保证每列至少有1
: 个1。
|
r****t
发帖数: 10904 | 7 没看懂，不是最少取m行就行了么？ 取 m-1 行不可能满足，m+1 行又比 m 多。
【在 h**6 的大作中提到】
: 不是一定从第一行起连续选取，可以从矩阵中任意取若干行。
|
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 的大作中提到】
: 已经一个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 的大作中提到】
: 已经一个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 |
