问题:鲍勃的销售

Question

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

鲍勃有一家商店,想要出售.他的商店里有很多产品,每种产品都有一定数量的单位库存.他还有许多货架价格标签(与产品数量一样多),价格已印在他们身上.他可以在任何产品上放置任何价格标签(该产品的整个库存的一件商品的单一价格),但是某些产品有额外的限制 - 任何此类产品可能不比某个其他产品便宜.

您必须找到如何安排价格标签,以便所有Bob的商品的总成本尽可能低.总成本是每个产品的分配价格标签的总和乘以库存中的产品数量.

---

鉴于:

• N - 产品数量和价格标签
• 小号_我,0≤ 我 <N -与指数产品的库存数量我(整数)
• P _Ĵ,0≤ Ĵ <N -价格标签上的价格与指数Ĵ(整数)
• K - 附加约束对的数量
• 甲_ķ,B _ķ,0≤ ķ <K -产品指数对附加的约束
  • 任何产品索引在B中最多可出现一次.因此,由该邻接列表形成的图实际上是一组有向树.

该计划必须找到:

• 中号_我,0≤ 我 <N -映射从产品索引到价格标签指数(P _中号我是产品的价格我)

满足条件:

1. P _中号甲ķ ≤P _中号乙ķ,对于0≤ ķ <K
2. Σ(S _我 ×P _中号我)为0≤ 我 <N是最小

---

请注意,如果不是第一个条件,解决方案将只是按价格和产品按数量对标签进行排序,并直接匹配.

输入的典型值为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包装)来显示.

令w ₁,...,w _n为3分区实例的对象的权重,令b为bin大小,k = n/3为允许填充的bin的数量.因此,如果可以对对象进行分区,则每个bin只有3个对象,则存在3分区.

对于减少,我们设置N = kb并且每个箱由相同价格的b价格标签表示(考虑P _i增加每个第b个标签).让吨_我,1≤ 我 ≤ ķ,是对应于该标签的价格我第斌.对于每瓦特_我我们有一个产物S _Ĵ数量的瓦特_我 + 1(让我们称之为本的根产品瓦特_我)和另一瓦特_我 - 1种产品的数量1,其被要求是除S便宜_Ĵ(称这些留下产品).

对于吨_我 =(2B + 1)^我,1≤ 我 ≤ ķ,有3分区当且仅当鲍勃可以卖2BΣ _{1≤ 我 ≤ ķ} 吨_我:

• 如果存在针对3分区的解决方案,那么对应于分配给相同仓的对象w _i,w _j,w _l的所有b个产品可以用相同的价格标记而不违反限制.因此,该解决方案已经花费2b中Σ _{1≤ 我 ≤ ķ}吨_我(因为产品具有价格总量吨_我是图2b).
  
• 考虑Bob's Sale的最佳解决方案.首先要注意的是,在任何解决方案中,超过3个根产品共享相同的价格标签,对于每个"太多"的根产品,有一个更便宜的价格标签,它坚持少于3个根产品.这比任何解决方案都要糟糕,因为每个价格标签(如果存在)正好有3个根产品.
  现在仍然可以找到Bob's Sale的解决方案,每个价格有3个根标签,但他们的休假产品不会使用相同的价格标签(垃圾箱流过).比如最昂贵的价格标签标记w _i的根产品,其具有更便宜的标记假产品.这意味着,3个标签W¯¯ _我,w ^ _Ĵ,w ^ _升标记了最昂贵的价格不加起来b.因此,标有此价格的产品的总成本至少为2b + 1.
  因此,这种解决方案具有成本t _k(2b + 1) +一些其他分配成本.因为对于一个存在3分区的最佳费用为2BΣ _{1≤ 我 ≤ ķ} 牛逼_我,我们必须表明,仅仅考虑的情况更糟糕.这种情况下,如果吨_ķ > 2BΣ _{1≤ 我 ≤ K-1} 吨_我(注意,这是K-1中的总和现在).设置吨_我 =(2B + 1)^我,1≤ 我 ≤ ķ,是这种情况.如果不是最昂贵的价格标签是"坏"价格标签,那也是如此,但任何其他价格标签.

所以,这是破坏性的部分;-)但是,如果不同价格标签的数量是常数,您可以使用动态编程在多项式时间内解决它.

Answer 2

这个问题类似于CS文献中考虑的许多调度问题.请允许我重申它.

问题("具有优先级,权重和一般迟到罚分的非抢先式单机调度")

输入:

• 工作1,...,n

• 工作中的"树状"优先关系(Hasse图是森林)

• 权重w ₁,...,w _n

• 从{1,...,n}到Z ₊的非递减的迟后罚函数L(t)

输出:

• 置换π的{1,...,N}最小化Σ _Ĵ瓦特_Ĵ L(π(j)的)受该对所有i PRECĴ我们有π(i)所述的约束<π(j)的.

通讯:工作<=>产品; 我预先j <=>我的价格低于j; 重量<=>数量; 值L(t)<=>吨^个最低价格

当L是线性时,由于Horn [1],存在一种有效的多项式时间算法.这篇文章是支付墙的背后,但主要的想法是

1. 对于所有j,找到仅包含j及其平均权重最大的后继的连接作业集.例如,如果n = 6并且优先约束是1 prec 2和2 prec 3和2 prec 4和4 prec 5,则考虑2的集合是{2},{2,3},{2,4 },{2,3,4},{2,4,5},{2,3,4,5}.我们实际上只需要最大平均权重,可以通过动态编程自下而上计算.

2. 按照相关集合的平均权重顺序安排工作.

在Cyber​​Shadow的例子中,我们有n = 10和1 prec 10和w _j = j和L(t)= t.在步骤1中计算的值是

• 工作1:5.5(平均1和10)

• 工作2:2

• 工作3:3

• 工作4:4

• 工作5:5

• 工作6:6

• 工作7:7

• 工作8:8

• 工作9:9

• 工作10:10

最佳顺序是9,8,7,6,1,10,5,4,3,2.

即使对于不同的L选择,该算法在实践中也可以很好地工作,因为最优性的证明使用局部改进.或者,也许CS Theory Stack Exchange上的某个人会有一个想法.

[1] WA Horn.具有树状优先级排序和线性延迟惩罚的单机作业排序.SIAM应用数学杂志,Vol.23,No.2(1972年9月),第189-202页.