寻找有效的算法(非平凡的)

Question

问题"规范":

这是圣诞节!你必须买礼物!

你有一套已经存在的玩具包,以及相应的捆绑价格:

1 0 0 1 0 1 1 1 0 => 58
0 1 0 0 1 1 1 0 0 => 27
1 1 1 0 0 0 1 0 0 => 46
0 0 0 0 1 1 1 1 0 => 73
...

a 1表示玩具在捆绑中,而a 0表示不在捆绑中.

现在,圣诞老人促销即将到来,并X以"特别促销价"向您提供剩余的包.如果存在另一个捆绑包,我们会说这X是一个糟糕的交易Y:

编辑:为了更容易,我删除了条件3,但将条件1从"子集"更改为"严格子集"

1. X是一个严格的子集Y
2. X 比...更贵 Y

目标是实现一种bool isBadSubset(X)能够有效地发现是否X好的功能.

鉴于存在数百万个捆绑包,将其与每个捆绑包进行比较显然是不可行的.此外,您可以假设在现有的捆绑集合中,玩具的子集总是比超集便宜.

提示:

• 比较一个集合是否是另一个集合的子集很容易
• 可以将比较限制为既包含至少N更多玩具又更便宜的比较.但是,列表可能仍然很大.
• 筛子方向的东西会很好
• 你不需要知道哪个捆绑更好......只是存在一个更好的捆绑

挑战:是否有可能在不变的时间内实现这一目标？(独立于目前集合中的捆绑数量)......或者至少在log(n)中？

Answer 1

好的，所以玩具的数量 n 是恒定且小的，即您有集合 {toy_0, .. toy_n-1}。

然后你可以有一个数组Set[n] bundleContainingToy，如果bundle x包含toy_i，那么你将x保存在setbundleContainingToy[i]中。

如果你得到一个新的bundle 1 0 0 1 0 1，你只需要计算bundleContainingToy[0]、bundleContainingToy[3]和bundleContainingToy[5]的交集。如果交集是 O(1) （您可以假设，因为您说过检查子集属性是），那么您也可以在 O(1) 中进行此检查，因为 n 是一个常数（而且很小）。

这是您要找的筛子吗？其余的计算仅取决于包含 toy_0、toy_3 和 toy_5 的包的数量。