将不同类别的商品分组以获得最大折扣 - java

Question

201 / 5.000 我目前在优化算法时遇到问题。这是一家提供多种不同商品的商店，这些商品分为 5 个不同类别（食品、饮料等）。

• 如果您购买两个不同类别的两种商品，您将获得这两种商品的 5% 折扣。
• 如果您购买 3 个不同类别，您将获得 10% 的折扣。
• 如果您购买 4 个不同类别，您将获得 20% 的折扣。
• 如果您购买 5 个不同类别，您将获得 25% 的折扣。

该算法应该优化任何购物的价格。

这里有一个示例，为简单起见，我假设每件商品的成本为 5 美元。

顾客购买

• 第 1 类中的 2 种商品，
• 第 2 类中的 2 种商品，
• 第 3 类中的 2 种商品，
• 类别 4 中的 1 项
• 类别 5 中的 1 项。

如果您组合 [1,2,3,4,5] 和 [1,2,3]，您将获得一次 25% 和一次 10% 折扣，总价为 32,25 美元。但如果将 [1,2,3,4] 和 [1,2,3,5] 分组，您将获得两倍的 20% 总价 32 美元。

Answer 1

如果我理解正确的话，你想优化购物车的总奖金。

解决方案1（适用于小购物车尺寸）

仅当您希望购物车仅包含少量商品时，才应使用此解决方案。在这种情况下，暴力方法应该不会有太大问题。

解决方案 2（适用于较大的购物车尺寸）

如果您的购物车太大而无法在合理的时间内尝试所有可能性，则一种可能性如下：

1. 将购物车分成与类别一样多的列表，并将所有商品分类到这些列表中。
2. 按价格（从最高到最低）对每个列表（应仅包含同一类别的商品）进行排序。
3. 创建一个列表，您可以在其中放置最终的项目组合。
4. 浏览每个类别列表并将项目放入最终列表中。

这应该会产生一个列表，其中最昂贵的项目组合是第一个。第一个条目也是具有最多不同类别项目的条目。在您的示例中，这将导致 {[1, 2, 3, 4, 5], [1, 2, 3]}。这个结果对于不同价格的物品来说是很好的，因为最昂贵的物品将属于较大的组。但由于这不是您的示例中具有相同价格的商品的最佳结果，因此您需要重新组织此结果。

要优化最后一个列表，您应该：

1. 计算每组的价格。
2. 将包含许多商品的一组价格与包含至少 2 件商品的一组价格进行比较。
3. 如果价格差异足够大，您可以从较大的组中取出一件商品并将其放入较小的组中。
4. 重复步骤 2 和 3，直到比较所有组的大小差异为 2

这可能不是最好的解决方案，但它应该很容易理解和实施。