algorithm - 问题 : Bob's Sale

Question

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

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

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

鉴于:

N——产品数量和价格标签

Si, 0≤i

Pj, 0≤j

K – 附加约束对的数量

Ak, Bk, 0≤k

任何产品索引在 B 中最多可能出现一次。因此，这个邻接表形成的图实际上是一组有向树。

该程序必须找到:

Mi, 0≤i
要满足条件:

PMAk ≤ PMBk，对于 0≤k

Σ(Si × PMi) 对于 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 打包)来显示。

设 w1, ..., wn 是 3-partition 实例的对象的权重，设 b 是 bin 大小，k = n/3 是允许填充的 bin 数量。因此，如果对象可以分区为每个 bin 正好有 3 个对象，则存在 3 个分区。

对于减少，我们设置 N=kb 并且每个 bin 由相同价格的 b 个价格标签表示(想想 Pi 增加每个第 b 个标签)。设 ti, 1≤i≤k, 是对应于第 i 个 bin 的标签的价格。
对于每个 wi，我们有一个数量为 wi + 1 的产品 Sj(我们称其为 wi 的根产品)和另一个数量为 1 的 wi - 1 产品，这些产品要求比 Sj 便宜(称之为休假产品)。

对于 ti = (2b + 1)i, 1≤i≤k，当且仅当 Bob 可以卖出 2bΣ1≤i≤k ti，存在 3 分:

如果存在 3-partition 的解决方案，那么分配到同一个 bin 的对象 wi, wj, wl 对应的所有 b 个产品都可以用相同的价格标记而不违反限制。
因此，该解决方案的成本为 2bΣ1≤i≤k ti(因为价格为 ti 的产品总量为 2b)。

考虑 Bob's Sale 的最优解。
首先观察，在任何解决方案中，超过 3 个根产品共享相同的价格标签，对于每个“太多”的此类根产品，都有一个更便宜的价格标签贴在少于 3 个根产品上。这比任何解决方案都糟糕，因为每个价格标签(如果存在)正好有 3 个根产品。
现在仍然可以有一个 Bob's Sale 的解决方案，每个价格有 3 个根标签，但他们的休假产品不带有相同的价格标签(垃圾箱有点流过)。
假设最昂贵的价格标签标记了 wi 的根产品，它具有更便宜的带标签的休假产品。这意味着用最昂贵的价格标记的 3 个根标签 wi、wj、wl 加起来不等于 b。因此，标有此价格的产品的总成本至少为 2b+1。
因此，这种解决方案的成本为 tk(2b+1) + 一些其他分配成本。由于现有 3-partition 的最优成本是 2bΣ1≤i≤k ti ，我们必须证明刚才考虑的情况更糟。如果 tk > 2b Σ1≤i≤k-1 ti(注意现在总和中是 k-1)，情况就是这种情况。设置ti = (2b + 1)i, 1≤i≤k，就是这种情况。这也适用，如果不是最昂贵的价格标签是“坏”的，但任何其他的。

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