s****h
发帖数: 3979 | 1 有个问题应该常见，可是想不好有什么现成的简单办法。
和推荐算法有点关系。
一群人，看过一堆书。
有完整的某人看过某书的信息
现在想拿到一个人，书，还有人书关系的子集，要求子集里每个人能看过不少于M本子
集里的书，子集里每本书不少于N个子集里的人看过。
好像唯一的方法就是狐狸分饼，越分越小。
while ！(集合里所有人都看过M＋本书，书都被N＋人看过）
｛
把不符合要求的书和人剔除出集合
｝ |
c***z
发帖数: 6348 | 2 Any subset or min subset? For any subset, just use the mother set.
For min subset, it is the min submatrix of a binary matrix with respect to:
1. row.sum >= M
2. col.sum >= N
I would try dynamic programming but I am brain dead to think about the
details now.
A heuristic is to move a 2Mx2N submatrix around to see if we get lucky. |
T*****u
发帖数: 7103 | 3 想法同上；第一个想法用graph表示书-人的关系，把小于m邻居的人node和小于n邻居的
书node一遍一遍的拆除，或者把满足的子集拆掉，基本一回事。如果这样的子集不止一
个（不相连的几个的合集），说不定有优势。 |
