optimization - 折扣分配问题（优化）

Question

假设我们有一家商店并销售5种不同的产品：A、B、C、D和E。 每种产品的固定基本成本为 8.00 美元。

现在我们将购买的每种产品的数量表示为一个元组(a, b, c, d, e)。以下是折扣规则：

• 仅 1 个不同的项目（例如(1,0,0,0,0)或(0,22,0,0,0)）：0%
• 2 个不同的项目（例如(1,2,0,0,0)）：5%
• 3 个不同的项目（例如(0,2,3,1,0)）：10%
• 4 种不同的物品：20%
• 5 种不同的物品：25%

例如，假设我们有(2,0,3,1,5)，所以 2x 产品 A，3x 产品 C，1x 产品 D，5x 产品 E。然后例如我们可以使用贪心方法：

(2,0,3,1,5) -> (1,0,2,0,4) -> (0,0,1,0,3) -> (0,0,0,0,2) -> (0,0,0,0,1) -> (0,0,0,0,0)

          (-20%)         (-10%)          (-5%)         (-0%)          (-0%)

每组不同的产品只能应用一次折扣。第一步，我们将其应用于 4 种不同的产品，因此($8.00 * 4) * 0.8，第二步我们将得到($8.00 * 3) * 0.90。

因此，如果我们在其中引入变量，那么我们通常会得到

totalPrice = [(base_price * n) * discountFor(n)] + [(base_price * (n-1)) * discountFor(n-1)] + ... + [(base_price * 2) * discountFor(2)] + (k * base_price)

我不允许使用幼稚的方法。玩了几个例子，我发现贪婪的方法非常稳定，但我不确定是否有反例。

我尝试正式写下问题，但这里没有明显的分析解决方案，因为我们可以使用特定折扣的频率取决于我们之前使用过的折扣。

有没有办法使用动态规划、线性规划或其他解决问题的技术来解决这个问题？

标签： optimizationdynamic-programmingmathematical-optimizationlinear-programming