如何从非重叠位集形成最大数量的 1 [英] How to form maximum number of 1s from non overlapping bitsets

问题描述

给定由 M 位组成的 N 个位集，选择 K 个位集，以便在同一位置不会出现多个 1.最多可以形成多少个 1?

Given N number of bitsets consisting of M bits, choose K bitsets such that there is no multiple 1s occurring in the same position. What is the maximum number of 1s that can be formed?

示例:

N = 5, M = 6
001100
011010
100100
111001
001010

答案将结合 011010 和 100100，其中答案是 5.

The answer would be combining 011010 and 100100, where the answer is 5.

我期待多项式时间解决方案，尽管我不确定是否可行.问题取自 here 可能有更好的措辞.

I expect a polynomial time solution, although I am not sure whether it is possible. The problem is taken from here with probably better phrasing.

推荐答案

这是加权最大集合打包 其中每个 bitset 被解释为一个集合，每个集合的权重是它的基数.

This is weighted maximum set packing where each bitset is interpreted as a set, and the weight of each set is its cardinality.

这篇关于如何从非重叠位集形成最大数量的 1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！