有N个编号为1到N的硬币。
你看不见它们,但是会收到关于它们的M个事实,形式如下:
struct Fact
{
set<int> positions
int num_heads
}
positions
指定了硬币的一个子集,num_heads
是该子集中正面朝上的硬币数量。
给定这些M个事实,您需要计算可能出现的最大正面朝上的硬币数。
这个问题是否为NP完全问题?如果是,那么它的归约是什么?如果不是,有什么多项式时间解决方案?
例如:
N = 5
M = 3
fact1 = { {1, 2}, 1 } // Either coin 1 or coin 2 is a head
fact2 = { {4}, 0 } // Coin 4 is a tail
fact3 = { {2, 4, 5}, 2 } // Out of coins 2, 4 and 5, two are heads
匹配事实的最佳配置为:
T H H T H
所以答案是3个头。