计算事物的最优列表

Question

问题陈述有5个桶。每种(许多)不同的产品。每个产品可以在同一桶中重复多次，也可以跨桶重复多次。我们想要推导出基于以下两个条件的产品:

1. 产品计数应该在桶中相当高
2. 相同的产品在每个细分市场中应该有相当高的数量

我要符合条件的产品清单。

我试过背包算法。通过提供随机权重和利润。这似乎是错误的方法

Answer 1

在线性时间内可以得到:

• 所有桶中每个产品的总数
• 桶中含有最少产品的每个产品的计数

如果线性时间太慢，在亚线性时间中，您可以通过采样桶来估计相同的时间。

无论哪种情况，您都拥有了做出决策所需的信息(或对信息的估计)。

在做了上面的事情之后，你需要决定你想要如何选择产品——本质上是你想要如何权衡每个产品的最小值和总数。