algorithm - 问题 : Bob's Sale

Question

注意:这是对 SWF 文件中有关排序记录的现实问题的抽象改写。解决方案将帮助我改进开源应用程序。

Bob 有一家商店，他想打折。他的商店有许多产品，并且他有一定数量的每种产品的库存。他还有一些货架上的价格标签(与产品数量一样多)，价格已经印在上面。他可以在任何产品上贴上任何价格标签(他的整个产品库存中一件商品的单一价格)，但是某些产品有额外的限制 - 任何此类产品不得比其他特定产品便宜。

您必须找到如何安排价格标签，使 Bob 所有商品的总成本尽可能低。总成本是每个产品的指定价格标签乘以该产品的库存数量的总和。

---

给定:

• N – 产品和价格标签的数量
• S_i, 0≤i i的产品的库存数量(整数)
• P_j, 0≤j j的价格(整数)
• K – 附加约束对的数量
• A_k, B_k, 0≤k
• 任何乘积索引在B中最多出现一次。因此，这个邻接表构成的图实际上是一组有向树。

程序必须找到:

• M_i, 0≤i M _i 是产品的价格 i)

满足条件:

1. P_MAk ≤ P_MBk，对于 0≤k
2. Σ(S_i × P_Mi) 对于 0≤ i

---

请注意，如果不是第一个条件，解决方案将是简单地按价格对标签进行排序，按数量对产品进行排序，然后直接匹配两者。

输入的典型值为 N,K<10000。在现实生活中，只有几个不同的价格标签 (1,2,3,4)。

---

这是为什么大多数简单的解决方案(包括拓扑排序)不起作用的一个例子:

您有 10 件商品，数量从 1 到 10，还有 10 个价格标签，价格从 1 美元到 10 美元。有一个条件:数量为 10 的商品不得比数量为 1 的商品便宜。

最优解是:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

总费用为 249 美元。如果您将 1,10 对放在任一极端附近，则总成本会更高。

Answer 1

对于一般情况，该问题是 NP 完全问题。这可以通过减少 3 分区来显示(这仍然是一个强大的 NP 完全版本的 bin packing)。

令 w₁, ..., w_n 为 3 分区实例的对象权重，令 b 是 bin 大小，k = n/3 是允许填充的 bin 数量。因此，如果可以对对象进行分区，使得每个容器恰好有 3 个对象，则存在 3 分区。

为了减少，我们设置 N=kb 并且每个 bin 由相同价格的 b 价格标签表示(想想 P_i 每 b 个标签递增)。设t_i, 1≤i≤k, 为对应标签的价格第 i 个箱子。对于每个 w_i，我们有一个产品 S_j，数量为 w_i + 1(我们称之为 w_i 的根积)和另一个 w_i - 1 数量 1 的产品，要求比 S_j 便宜(称这些为休假产品)。

对于t_i = (2b + 1)ⁱ, 1≤i≤k ，当且仅当 Bob 可以卖出 2bΣ_{1≤i≤k 时，才有 3 分区} t_i:

• 如果存在3-划分的解，则所有b个积对应对象w_i，w< sub>j, w_l 分配到同一个 bin 的可以在不违反限制的情况下标注相同的价格。因此，解决方案的成本为 2bΣ_1≤i≤k t_i(因为价格为 t_i 的产品总数为 2b)。
  
• 考虑 Bob 销售的最优解。首先观察在任何解决方案中，超过 3 个根产品共享相同的价格标签，对于每个“太多”的根产品，有一个更便宜的价格标签贴在少于 3 个根产品上。如果每个价格标签(如果存在)恰好有 3 个根产品，这比任何解决方案都要糟糕。
  现在 Bob's Sale 仍然可以有一个解决方案，每个价格有 3 个根标签，但是他们的休假产品没有贴上相同的价格标签(箱子有点溢出)。假设最昂贵的价格标签标记了 w_i 的根产品，它有一个更便宜的标记离开产品。这意味着 3 个根标签 w_i、w_j、w_{l<标有最贵价格的/sub>} 加起来不等于 b。因此，标有此价格的产品的总成本至少为 2b+1。
  因此，这样的解决方案具有成本 t_k(2b+1) + 一些其他分配成本。由于现有 3 分区的最佳成本是 2bΣ_1≤i≤k t _i ，我们必须证明刚刚考虑的情况更糟。如果 t_k> 2b Σ_{1≤i≤k-1/sub> ti(请注意现在总和为 k-1)。设 ti = (2b + 1)ⁱ, 1≤i≤k，是这样的。如果不是最昂贵的价格标签是“坏”的，而是其他任何价格，这也适用。}

所以，这是破坏性的部分;-) 但是，如果不同价格标签的数量是常数，则可以使用动态规划在多项式时间内求解。