algorithm - 问题 : Bob's Sale

标签 algorithm

注意:这是对 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 对放在任一极端附近,总成本会更高。

  • 最佳答案

    对于一般情况,问题是 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,就是这种情况。这也适用,如果不是最昂贵的价格标签是“坏”的,但任何其他的。

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

    关于algorithm - 问题 : Bob's Sale,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4898511/

    相关文章:

    java - 有效地搜索“关闭点”

    使用正则表达式的 Python 跨文件搜索

    arrays - 从数组A构造数组B,每个索引都是原始数组中第k个元素的最大值

    algorithm - 在集合中查找最小值/最大值时,使用一种类型的最小值/最大值

    c++ - 在 C++ 中求解 Ax = b, A = 下三角矩阵

    algorithm - 递归回溯的子集总和

    algorithm - 合并排序的大o

    c++ - 用于加速汇总循环的多线程 C++ 程序

    algorithm - 如果NP在多项式时间内求解,可满足性可以在多项式时间内求解

    algorithm - 在int中找到第n个SET位