-2

有n个项目,每个项目的长度为b。物品上写的不同条形码仅由 0 和 1 组成。我们需要将物品放入袋中,但有条件。大多数条码只有 1 位或 2 位不同。因此,如果一个物品与该袋子的所有其他物品有超过 2 个不同的位,我们只能将它放入另一个袋子。怎么找没有。需要的袋子。

约束:

1 <= N <= 10,000

1 <= B <= 32

第一行包含两个空格分隔的整数 N 和 B。

N:携带物品数量,B:每个条码的长度。

例子:

5 6

1 1 1 1 1 1

0 0 0 0 1 0

1 1 0 0 0 1

1 1 1 0 0 0

1 0 0 0 0 0

其中 5 是编号。项目和每个项目的 6 个长度。

结果:2

解释:

第一项与其余所有项的差异超过 2 位,因此它位于 Bag 1 中。

第 2 项和第 5 项有 2 位不同,因此它们可以组合在一起。

3rd 和 4th 也只有 2 个不同的位,因此它们也可以放入同一个袋子中。

第 5 位与除第 1 位以外的所有其他位只有 2 个不同的位,因此 2、3、4、5 全部组合在 Bag 2 中。

4

2 回答 2

1

第一步是制作图表:

节点是项目。连接每一对不允许一起走的物品!

其次,将其作为着色问题来解决。网上有很多解决方法

完毕 ;-)

顺便说一句,它是 NP Hard,所以启发式方法是个好主意!

于 2013-09-30T18:42:02.683 回答
1

如果我们将每个条形码的 1 的数量存储在一个数组中,按升序对其进行排序,遍历每个元素,然后计算两个大于 2 的相邻元素之间的差异,例如。数组 [6,1,3,3,1], sorted => [1,1,3,3,6] 答案是 2....

这个解决方案会起作用吗..??

于 2013-10-01T11:43:00.923 回答