在一个集合中找出最不同的元素

Question

假设我们有一家香水店，有100种不同的香水。假设10,000名顾客来到店内，为每种香水评分，评分从一星到五星。问题是：“如何最好地构建一个由5种香水组成的套装，以便95%的顾客会至少为其中一种给出4星或以上的评价?”如何进行算法处理？

注意：我可以看到这个问题本身并没有准确表述；不存在这样的结构的保证。存在两个参数之间的权衡。

另外，（这使得香水类比稍微有些人为），获得一个良好的匹配还是三个良好的匹配并没有关系。所以{4.3,0,0,0,0}等同于{4.3,4.2,4.2,4.2,4.2}--在两种情况下分数都是4.3。

假设为了论证，香水0-19是甜的，香水20-39是酸的等等（相似盐，苦味，鲜味）。因此，0-19之间会有非常高的交叉相关性。

如果你用100个点在空间中建模，那么0-19会非常强烈地互相吸引，它们会形成一个集群。同样，你会得到另外四个集群，表示其他四种味道。

因此，从一个指标中，我们分出了5种不同的口味。但这种技术是否扩展到其他场景呢？

PS：提供相关技术名称将非常有帮助，因为这样可以让我在谷歌上搜索更多信息。因此，任何只是用行业公认术语重新陈述问题的答案都会很有用！

- P i

---

选择一个4-5星级的香水，再选4个1-3星级的香水，重复此步骤。或者我漏掉了什么？ - Bernhard Barker

看起来像是最大覆盖问题。其中k=5，顾客被称为“元素”，给某种香水评价4星或以上的顾客形成一个“集合”。 - Evgeny Kluev

你正在寻求一个算法，但你自己并没有尝试去创建一个。这和“请发代码”没有什么区别。 - Raedwald

Answer 1

该算法应该解决以下问题：

1. 按给出4+评分的客户数量对香水进行排序
2. 从列表中选择尚未考虑过的第一种香水
3. 删除现在满意的客户的评分。
4. 重复处理包装中2-5种香水的过程。

必要时回溯以获得符合标准的选择。

- Terje D.

Answer 2

真正的问题是NP难问题，但你可以利用贪心算法：

1. 将C定义为所有客户。
2. 为每种香水分配一个覆盖范围，该覆盖范围由C中给予每种香水4+的客户数量确定
3. 按覆盖面积降序排序。如果C为空且所有覆盖面积都为零，则随机选择一种香水（实际上，如果C非零但小于原始值的5％，则满足您的要求）
4. 从C中删除已选择的香水满足的所有客户（不是评级）
5. 除非您已经有5种香水，否则请从2开始重复。

这自动处理了口味聚类：给甜香水高分的客户将满意于最受欢迎的甜香水，并且他将被从C中清除，忽略他的所有进一步评级，然后算法将继续满足其他客户。

此外，您应该注意，即使您无法使用五种香水满足要求（95％，4+），香水相似性也将确保此算法最大化覆盖率和得分-因此您可能最终会得到（93％，3.9）。

此外，假设有10％的用户没有给出3分以上的任何评分。由于总数中有至多3个可满足的10％，因此绝无可能4满意95％的客户。您可能希望使用实际上至少给出一个4+评分的客户来构建C。

或者，您可以更改算法，而不是使用您问题中的算法，决定使用背包：您想带回家最高的累计评分。这也提高了客户对整体套餐满意度的可能性（目前，他几乎可以保证非常喜欢其中的一种香水，但他可能强烈不喜欢其他四种）。

- LSerni