注意:这是对 SWF 文件中有关排序记录的现实问题的抽象改写。解决方案将帮助我改进开源应用程序。
Bob 有一家商店,他想打折。他的商店有许多产品,并且他有一定数量的每种产品的库存。他还有一些货架上的价格标签(与产品数量一样多),价格已经印在上面。他可以在任何产品上贴上任何价格标签(他的整个产品库存中一件商品的单一价格),但是某些产品有额外的限制 - 任何此类产品不得比其他特定产品便宜。
您必须找到如何安排价格标签,使 Bob 所有商品的总成本尽可能低。总成本是每个产品的指定价格标签乘以该产品的库存数量的总和。
给定:
- N – 产品和价格标签的数量
- Si, 0≤i
i的产品的库存数量(整数) - Pj, 0≤j
j的价格(整数) - K – 附加约束对的数量
- Ak, Bk, 0≤k
- 任何乘积索引在B中最多出现一次。因此,这个邻接表构成的图实际上是一组有向树。
程序必须找到:
- Mi, 0≤i
M i 是产品的价格 i)
满足条件:
- PMAk ≤ PMBk,对于 0≤k
- Σ(Si × PMi) 对于 0≤ i
- Σ(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 对放在任一极端附近,则总成本会更高。
最佳答案
对于一般情况,该问题是 NP 完全问题。这可以通过减少 3 分区来显示(这仍然是一个强大的 NP 完全版本的 bin packing)。
令 w1, ..., wn 为 3 分区实例的对象权重,令 b 是 bin 大小,k = n/3 是允许填充的 bin 数量。因此,如果可以对对象进行分区,使得每个容器恰好有 3 个对象,则存在 3 分区。
为了减少,我们设置 N=kb 并且每个 bin 由相同价格的 b 价格标签表示(想想 Pi 每 b 个标签递增)。设ti, 1≤i≤k, 为对应标签的价格第 i 个箱子。 对于每个 wi,我们有一个产品 Sj,数量为 wi + 1(我们称之为 wi 的根积)和另一个 wi - 1 数量 1 的产品,要求比 Sj 便宜(称这些为休假产品)。
对于ti = (2b + 1)i, 1≤i≤k ,当且仅当 Bob 可以卖出 2bΣ1≤i≤k 时,才有 3 分区 ti:
- 如果存在3-划分的解,则所有b个积对应对象wi,w< sub>j, wl 分配到同一个 bin 的可以在不违反限制的情况下标注相同的价格。
因此,解决方案的成本为 2bΣ1≤i≤k ti(因为价格为 ti 的产品总数为 2b)。
- 考虑 Bob 销售的最优解。
首先观察在任何解决方案中,超过 3 个根产品共享相同的价格标签,对于每个“太多”的根产品,有一个更便宜的价格标签贴在少于 3 个根产品上。如果每个价格标签(如果存在)恰好有 3 个根产品,这比任何解决方案都要糟糕。
现在 Bob's Sale 仍然可以有一个解决方案,每个价格有 3 个根标签,但是他们的休假产品没有贴上相同的价格标签(箱子有点溢出)。 假设最昂贵的价格标签标记了 wi 的根产品,它有一个更便宜的标记离开产品。这意味着 3 个根标签 wi、wj、wl<标有最贵价格的/sub> 加起来不等于 b。因此,标有此价格的产品的总成本至少为 2b+1。
因此,这样的解决方案具有成本 tk(2b+1) + 一些其他分配成本。由于现有 3 分区的最佳成本是 2bΣ1≤i≤k t i ,我们必须证明刚刚考虑的情况更糟。如果 tk> 2b Σ1≤i≤k-1/sub> ti(请注意现在总和为 k-1)。设 ti = (2b + 1)i, 1≤i≤k,是这样的。如果不是最昂贵的价格标签是“坏”的,而是其他任何价格,这也适用。
所以,这是破坏性的部分;-) 但是,如果不同价格标签的数量是常数,则可以使用动态规划在多项式时间内求解。
关于algorithm - 问题 : Bob's Sale,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4898511/