问题：鲍勃的销售

注意：这是关于在SWF文件中sortinglogging的真实问题的抽象重新说明。 一个解决scheme将帮助我改进一个开源应用程序。

鲍勃有一家商店，并希望做一个销售。 他的商店里有很多产品，他有一定数量的每种产品的库存单位。 他还有一些货架上的价格标签（与产品数量一样多），已经印上价格。 他可以在任何产品上放置任何价格标签（整个产品的单一价格），但是有些产品有额外的限制 – 任何这样的产品可能不会比某些其他产品便宜。

你必须find如何安排价格标签，使鲍勃所有产品的总成本尽可能低。 总成本是每个产品的分配价格标签乘以库存产品数量的总和。

---

鉴于：

• N – 产品数量和价格标签
• S _i ，0≤i<N – 具有索引i的产品的数量（整数）
• P _j ，0≤j<N – 具有索引j的价格标签上的价格（整数）
• K – 附加约束对的数量
• A _k ，B _k ，0≤k<K – 附加约束的乘积
  • 任何产品索引在B中最多只能出现一次。因此，由这个邻接表形成的graphics实际上是一组有向的树。

该计划必须find：

• M _i ，0≤i<N – 从产品指标到价格标签指数的映射（P _{M i}是产品i的价格）

为了满足条件：

1. P _{M A} k≤PM _{B k} ，0≤k<K
2. Σ（S _i ×P _{M i} ）对于0≤i<N是最小的

---

请注意，如果不是第一个条件，解决scheme将简单地按价格和产品按数量分类标签，并直接匹配。

典型的input值是N，K <10000。 在现实生活中，只有几个不同的价格标签（1,2,3,4）。

---

下面是为什么大多数简单解决scheme（包括拓扑sorting）不起作用的一个例子：

数量为1到10的商品有10个，价格为$ 1到$ 10的价格标签为10个。 有一个条件：数量为10的物品不能比数量为1的物品便宜。

最佳解决scheme是：

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完全的。 这可以通过减less3分区来显示（这是一个仍然强大的NP装箱版本）。

假设w ₁ ，…，w _n是3分区实例的对象的权重，设b是容器大小，并且k = n / 3是允许填充的容器的数量。 因此，如果可以对对象进行分区，那么就有一个3分区，每个分区恰好有3个对象。

为了减less，我们设置N = kb ，每个bin由相同价格的b个价格标签表示（假设P _i每增加一个标签）。 令t _i ，1≤i≤k为第i个仓位对应的标签价格。 对于每一个我们我们有一个产品S _j的数量w _i + 1 （让我们称之为w _i的根产品）和另一个需要比S _j便宜的数量为1的产品（称这些产品为留下产品）。

对于t _i =（2b + 1） ⁱ ，1≤i≤k，存在一个3分区当且仅当Bob可以卖给_{2bΣ1≤i≤kt i} ：

• 如果存在3分区的解决scheme，则与分配给同一分区的对象w _i ， w _j ， w _l相对应的所有b个产品可以用相同的价格标记，而不违反限制。 因此，解决scheme的成本为_{2bΣ1≤i≤k} t _i （因为价格t _i的产品总量为2b ）。
• 考虑Bob's Sale的最佳解决scheme。 首先要观察的是，在任何解决scheme中，超过3个根产品共享相同的价格标签，对于每个“太多”的根产品，存在更便宜的价格标签，其贴在less于3个根产品上。 这比任何解决scheme都差，每个价格标签只有3个根产品（如果存在的话）。
  现在仍然可以有一个Bob's Sale的解决scheme，每个价格有三个根标签，但是他们的产品不会佩戴相同的价格标签。 说最昂贵的价格标签标签w _我有一个更便宜的标签假产品的根产品。 这意味着以最昂贵的价格标记的3个根标签w _i ， w _j ， w _l不等于b 。 因此，以这个价格标记的产品的总成本至less为2b + 1 。
  因此，这样的解决scheme的成本为t _k （2b + 1） +其他一些分配成本。 由于现有的3分区的最优成本是_{2bΣ1≤i≤kt i} ，我们必须certificate刚刚考虑的情况更糟糕。 如果t _k > _{2bΣ1≤i≤k -1} t _i （注意它现在是k-1） ，那就是这种情况。 设置t _i =（2b + 1） ⁱ ，1≤i≤k，情况如此。 这也成立，如果不是最昂贵的价格标签是“坏”的，但任何其他。

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

Answer 2

这个问题类似于CS文献中考虑的许多调度问题。 请允许我将它重新归类为一个。

问题 （“具有优先权的非抢先式单机调度，权重和一般迟后惩罚”）

input：

• 工作1，…，n

• 作业中的“树状”优先关系（哈斯图是森林）

• 权重w ₁ ，…，w _n

• 从{1，…，n}到Z ₊的非递减迟后惩罚函数L（t）

输出：

• π（j）满足约束条件，对于所有的i prec j，我们有π（i）<π（j）的置换π{1，…，n}。

信函：工作<=>产品; 我预测j <=>我的价格比j低。 重量<=>数量; L（t）<=> ^第 t ^个最低价格

当L是线性时，由于Horn [1]，有一个有效的多项式时间algorithm。 这篇文章是在付费墙背后，但主要的想法是

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

2. 贪婪地安排工作，按其相关组合的平均重量sorting。

在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的不同select，该algorithm也可能在实践中运行良好，因为最优性certificate使用局部改进。 或者，也许CS Theory Stack Exchange上的某个人会有一个想法。

[1] WA Horn。 具有Treelike优先顺序和线性延迟罚函数的单机作业sorting 。 SIAM应用math杂志，Vol。 23，No.2（1972年9月），第189-202页。

Answer 3

由于我认为这个问题很有趣，所以我做了一个使用约束规划寻找解决scheme的模型。 该模型是用称为MiniZinc的build模语言编写的 。

 include "globals.mzn"; %%% Data declaration % Number of products int: n; % Quantity of stock array[1..n] of int: stock; % Number of distinct price labels int: m; % Labels array[1..m] of int: labels; constraint assert(forall(i,j in 1..m where i < j) (labels[i] < labels[j]), "All labels must be distinct and ordered"); % Quantity of each label array[1..m] of int: num_labels; % Number of precedence constraints int: k; % Precedence constraints array[1..k, 1..2] of 1..n: precedences; %%% Variables % Price given to product i array[1..n] of var min(labels)..max(labels): prices :: is_output; % Objective to minimize var int: objective :: is_output; %%% Constraints % Each label is used once constraint global_cardinality_low_up_closed(prices, labels, num_labels, num_labels); % Prices respect precedences constraint forall(i in 1..k) ( prices[precedences[i, 1]] <= prices[precedences[i, 2]] ); % Calculate the objective constraint objective = sum(i in 1..n) (prices[i]*stock[i]); %%% Find the minimal solution solve minimize objective; 

一个问题的数据在一个单独的文件中给出。

 %%% Data definitions n = 10; stock = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; m = 10; labels = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; num_labels = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]; k = 1; precedences = [| 1, 10 |]; 

这个模式相当幼稚，直截了当，没有花哨的东西。 使用Gecode后端解决示例问题，会生成以下输出（假设模型位于model.mzn中，数据位于data.dzn中）

 $ mzn2fzn -I/usr/local/share/gecode/mznlib/ model.mzn data.dzn $ fz -mode stat -threads 0 model.fzn objective = 265; prices = array1d(1..10, [1, 10, 9, 8, 7, 6, 5, 4, 3, 2]); ---------- objective = 258; prices = array1d(1..10, [2, 10, 9, 8, 7, 6, 5, 4, 1, 3]); ---------- objective = 253; prices = array1d(1..10, [3, 10, 9, 8, 7, 6, 5, 2, 1, 4]); ---------- objective = 250; prices = array1d(1..10, [4, 10, 9, 8, 7, 6, 3, 2, 1, 5]); ---------- objective = 249; prices = array1d(1..10, [5, 10, 9, 8, 7, 4, 3, 2, 1, 6]); ---------- ========== %% runtime: 0.027 (27.471000 ms) %% solvetime: 0.027 (27.166000 ms) %% solutions: 5 %% variables: 11 %% propagators: 3 %% propagations: 136068 %% nodes: 47341 %% failures: 23666 %% peak depth: 33 %% peak memory: 237 KB 

对于更大的问题，这当然要慢得多，但是随着时间的推移，模​​型通常会产生更好的解决scheme。

Answer 4

作为一个社区维基发表一些想法，随时编辑。

如果考虑到附加的限制条件，这个问题就更容易看出来，因为必须按照每个节点必须位于其父节点右侧的方式来布局或重新排列一组从上到下的树（左侧的产品是便宜，右边的更贵）。

假设两种产品相互冲突，如果第一种产品比第二种产品多，而第一种产品不能比其他产品便宜（因此它们在价格上被“拉”到不同的方向）。 同样，冲突的一组产品是至less有两种产品冲突的产品，其产品没有一个产品与组外的任何产品发生冲突。

我们可以做一些观察：

1. 当“放置”（分配价格标签）两个相冲突的产品时，它们将总是彼此相邻。
2. 如果按照数量sorting所有产品而不考虑约束条件，然后进行最优排列以满足约束条件，那么冲突组中所有产品的最终位置总是在产品的最左边和最右边的初始位置之间（包含）。
3. 因此，如果可以通过从树中删除单个右指向边来将约束树分成两部分，以便产品从底部子树到树根path的初始位置范围不重叠，则可以安全将它们视为两个不同的约束树（或单个节点），并忘记它们之间存在依赖关系。 （ 简单的例子 ）

algorithm思想：

1. 首先，放置所有不受限制的产品。
2. 对于每个约束树：
   1. 将其分割成所有右侧边缘（非冲突产品之间的边缘）的子树。 我们现在有一组所有边都指向左边的子树。
   2. 对于每个子树：
      1. 获取它的拓扑sorting列表
      2. 试着从这个子树中产品的从最低到最高的起始位置开始的每一个位置插入这个列表，确定产生最低总价的那个
   3. 对于步骤2.1中删除的每个边缘：
      1. 如果两个子树的新位置是“相冲突的”：
         1. 将较高级别与较低级别（拓扑sorting的特例）
         2. 同样尝试find连接列表的最佳位置
         3. 为了将来合并，将两个检查的子树作为一个子树

这个algorithm的主要问题是如何处理已经放置的约束对的位移。 我想，只是试图通过迭代search重新放置stream离失所的链可能工作，但algorithm已经看起来太复杂，无法正确工作。

在不同价格数量较低的情况下，您可以为每个不同的价格使用一个双向链接列表（或双向链接列表），将所有价格分配给它们的商品。 deques是从最低到最高价格。 将一个项目插入到一个双端转换器中，将最后一个项目转换为下一个deque的开始（对于下一个更高的不同价格），以此类推。

有一点需要注意的是迭代/冒泡sortingalgorithm：当你有一对冲突的产品时，贪婪地走向任何一个方向是不够的，直到下一个产品没有产生改进。 这里有一个testing用例，我用Mathematica写一个testing用例生成器，

 Price, $ 1 2 7 9 Qty 3 2 1 4 

约束条件是让1-qty项目的右侧有4-qty项目。 如上所示，总价格是50美元。 如果你将这一对移动到左边一个位置（所以它是3 1 4 2 ），总数将上升到51美元，但是如果你再往前走（ 1 4 3 2 ），它就会下降到48美元。

Answer 5

这是对Gero答案的后续。 这个想法是修改他的结构，以performance出很强的NP-硬度。

而不是select$ t_i =（2b + 1）^ i $，select$ t_i = i $。 现在，你必须修改一个论点，即一个带有奖励的解决scheme意味着存在一个3分区。

采取任意架子顺序。 按照以下方式进行会计核算：将$ w_i-1 $单位数量的根产品分配给其叶产品。 然后每个产品都有数量2.根据约束的定义，这不会转移到更高的价格。 在这个转换之后，价格将正好是$ P $。 如果转移一些数量到一个较低的奖品，原来的奖品严格大于$ P $。

因此，如果所有的叶子产品都具有与其根产品相同的奖励，则意味着存在一个三分区，这是唯一可能的。

引用SWAT 2010年论文的结果，这个论点表明即使对数字和$ k $不同价格标签进行一元编码，运行时间为$ f（k）\ cdot n ^ {O（1）} $也会违反“标准复杂性假设“。 这使得在运行时间为$ n ^ {O（k）} $的dynamic编程中显得不那么糟糕。

---

这是从同一个答案在cstheory交叉发布。

Answer 6

您可以先尝试解决简单的情况，您只需按价格和产品按数量对标签进行sorting，然后直接进行匹配，然后对这个第一个近似值使用演化过程：生成有序的产品列表的随机变化，将less量随机select的项目在列表中上下移动几个位置，计算列表中每个变体的总成本，保留最less的几个，并将其作为下一代的基础。 迭代这个过程在许多代人最终，我希望，给你正确的答案你的问题，在一小部分的时间，将蛮力的解决scheme。

Answer 7

攻击这个问题的一个方法是用0-1线性规划来expression它，并用Balas的加法algorithm来解决它。 以下是如何编码的问题：

• variables： N ^2个二进制variables。 为了清楚起见，我将用两个整数对它们进行索引：当且仅当产品i被赋予标签j时， x _ij是1 。
• 目标函数：最小化S _i P _j x _ij （表示原始目标函数）的i和j之和。
• 约束条件：对于P _j x _{A k} j – P _j x _{B k} j的每个k和j ， ≤≤ （表示原始价格约束）。
• 约束条件：对于每个i的x _ij的总和j是1 ; 对于x _ij中的每个j的和i是1 （表示x编码置换）。

我不是线性规划方面的专家，可能存在更高效的编码。

Answer 8

以字典顺序生成价格排列 ，并返回符合约束的第一个排列 。

假设产品和价格已经分类（最低，分别是最高，最高和最低），

1. 当0 <= k < n且l[n] = 0设置l[k] = k+1 。 然后设置k = 1 。
2. 设置p = 0, q = l[0] 。
3. 设置M[k] = q 。 如果任何具体涉及P[k]价格约束失败，则转到5.否则，如果k = n ，则返回M[1]...M[n] 。
4. 设u[k] = p, l[p] = l[q], k = k + 1并且转到2。
5. 设p = q, q = l[p] 。 如果q != 0转到3。
6. 设置k = k - 1 ，如果k = 0终止。 否则，设定p = u[k], q = M[k], l[p] = q并转到5。

这是Knuth计算机编程艺术（第4卷，分册2，第7.2.1.2节）的algorithmX（略作修改）。 与Knuth的大部分algorithm一样，它使用基于1的索引。 将它编入适合您典型编程语言的基于0的索引，我将其作为读者的练习。

编辑：

不幸的是，事实certificate，这并不能保证一个非递减的序列。 我将不得不更多地考虑是否可以挽救这个问题。