algorithm - 非重叠购买的最佳顺序

Question

我认为这是一个日程安排问题，但我什至不确定那么多!我想要的是找到最佳的非重叠购买决策序列，当我充分了解它们的值(value)以及 future 会出现什么机会时。

想象一下，一个批发商销售我想为自己的商店购买的各种商品。在任何时候，他们都可能有多个特别优惠事件；我会全价出售，所以他们的折扣就是我的利润。

我想最大化利润，但问题是我一次只能买一件东西，而且没有信用，更糟糕的是，还有交货延迟。好消息是我会在货到货后立即卖掉，然后我就可以再花钱了。因此，通过所有选择的一条路径可能是:我在星期一购买 100 公斤苹果，它们在星期二交付。然后我购买了 20 件修女服装，在星期天送达，足够合适。我跳过了几天，因为我知道周三他们将以大幅折扣出售法拉利。所以我买了其中一个，它在下周二交付。等等。

您可以考虑复合利润或不复合利润。该算法归结为在每个阶段做出决定，是选择今天的特别优惠之一，还是等待一天，因为明天会有更好的东西。

让我们抽象一下。购买和交付成为时代以来的天数。利润表示为卖出价除以买入价。 IE。 1.00 表示收支平衡，1.10 表示 10% 的利润，2.0 表示我的钱翻了一番。

  buy    delivery   profit
    1        2       1.10    Apples
    1        3       1.15    Viagra
    2        3       1.15    Notebooks
    3        7       1.30    Nun costumes
    4        7       1.28    Priest costumes
    6        7       1.09    Oranges
    6        8       1.11    Pears
    7        9       1.16    Yellow shoes
    8       10       1.15    Red shoes
   10       15       1.50    Red Ferrari
   11       15       1.40    Yellow Ferrari
   13       16       1.25    Organic grapes
   14       19       1.30    Organic wine

注意:机会只存在于购买日(例如，如果没有人购买，有机葡萄就会被制成 Wine !)，我可以在交货的同一天出售，但直到购买日才能购买我的下一件商品次日。所以我不能在 t=7 卖掉我的修女服装，然后在 t=7 立即买黄色鞋子。

我希望存在一个已知的最佳算法，并且已经有一个 R 模块，但算法或学术文献也很好，任何其他语言的任何东西都一样。速度很重要，但主要是当数据变大时，所以我想知道它是 O(n²) 还是其他。

顺便问一下，如果存在最大可能的交付延迟，最佳算法会改变吗？例如。如果delivery - buy <= 7

以上数据为 CSV 格式:

buy,delivery,profit,item
1,2,1.10,Apples
1,3,1.15,Viagra
2,3,1.15,Notebooks
3,7,1.30,Nun costumes
4,7,1.28,Priest costumes
6,7,1.09,Oranges
6,8,1.11,Pears
7,9,1.16,Yellow shoes
8,10,1.15,Red shoes
10,15,1.50,Red Ferrari
11,15,1.40,Yellow Ferrari
13,16,1.25,Organic grapes
14,19,1.30,Organic wine

或者作为 JSON:

{"headers":["buy","delivery","profit","item"],"data":[[1,2,1.1,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.3,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.5,"Red Ferrari"],[11,15,1.4,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.3,"Organic wine"]]}

或者作为 R 数据框:

structure(list(buy = c(1L, 1L, 2L, 3L, 4L, 6L, 6L, 7L, 8L, 10L, 
11L, 13L, 14L), delivery = c(2L, 3L, 3L, 7L, 7L, 7L, 8L, 9L, 
10L, 15L, 15L, 16L, 19L), profit = c(1.1, 1.15, 1.15, 1.3, 1.28, 
1.09, 1.11, 1.16, 1.15, 1.5, 1.4, 1.25, 1.3), item = c("Apples", 
"Viagra", "Notebooks", "Nun costumes", "Priest costumes", "Oranges", 
"Pears", "Yellow shoes", "Red shoes", "Red Ferrari", "Yellow Ferrari", 
"Organic grapes", "Organic wine")), .Names = c("buy", "delivery", 
"profit", "item"), row.names = c(NA, -13L), class = "data.frame")

链接

Are there any R Packages for Graphs (shortest path, etc.)? (igraph 提供了一个 shortest.paths 函数，除了 C 库之外，还有一个 R package 和一个 python 接口(interface))

Answer 1

思考这个问题的最简单方法类似于 shortest-path problem (尽管将其视为 maximum flow problem 在技术上可能更好)。日期编号 1 ... 19 可用作节点名称；每个节点 j 都有一个指向权重为 1 的节点 j+1 的链接，并且每个产品 (b,d,g,p)列表添加一个从第 b 天到第 d+1 天的链接，权重为 g。当我们在寻路时通过节点时，我们会跟踪到目前为止在每个节点看到的最佳乘积值。

下面显示的 Python 代码运行时间为 O(V+E)，其中 V 是顶点数(或天数)，E 是边数。在此实现中，E = V + 正在销售的产品数量。 添加注释:循环 for i, t in enumerate(graf): 对每个顶点处理一次。在该循环中，for e in edges: 处理来自当前顶点的每条边一次。因此，没有一条边被处理超过一次，所以性能是 O(V+E)。

编辑注释 2: krjampani 声称 O(V+E) 比 O(n log n) 慢，其中 n 是产品的数量。但是，除非我们对所考虑的天数做出假设，否则这两个订单不可比。请注意，如果交货延迟有限且产品日期重叠，则天数为 O(n)，因此 O(V+E) = O(n)，这比 O(n log n) 更快。

但是，在一组给定的假设下，我的方法和 krjampani 的运行时顺序可以相同:对于大量的天数，更改我的方法以仅在 x[0] 的排序联合中为天数创建图节点和 x[1] 值，并使用指向 day[i-1] 和 day[i+1] 的链接而不是指向 i-1 和 i+1 的链接。对于少量天数，将 krjampani 的方法更改为使用 O(n) 计数排序。

程序的输出如下所示:

 16 :   2.36992 [11, 15, 1.4, 'Yellow Ferrari']
 11 :   1.6928 [8, 10, 1.15, 'Red shoes']
 8 :    1.472 [4, 7, 1.28, 'Priest costumes']
 4 :    1.15 [1, 3, 1.15, 'Viagra']

这表明我们在第 15 天卖出黄色法拉利后，在第 16 天获得了 2.36992 的复合利润；在第 11 天卖出红鞋后获利 1.6928；等等。请注意，产品列表开头的虚拟条目以及数字周围引号的删除是与 JSON 数据的主要区别。列表元素 graf[j] 中的条目以 [1, j-1, 0, [[j+1,1,0]]] 开头，即，形式为 [best-value-so-far, best-from-node#, best-from-product-key, edge-list]。每个边缘列表都是列表的列表，其形式为 [next-node#, edge-weight, product-key]。将产品 0 设为虚拟产品可简化初始化。

products = [[0,0,0,""],[1,2,1.10,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.30,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.50,"Red Ferrari"],[11,15,1.40,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.30,"Organic wine"]]
hiDay = max([x[1] for x in products])
graf = [[1, i-1, 0, [[i+1,1,0]]] for i in range(2+hiDay)]

for i, x in enumerate(products):
    b, d, g, p = x[:]
    graf[b][3] += [[d+1, g, i]] # Add an edge for each product

for i, t in enumerate(graf):
    if i > hiDay: break
    valu = t[0]                 # Best value of path to current node
    edges = t[3]                # List of edges out of current node
    for e in edges:
        link, gain, prod = e[:]
        v = valu * gain;
        if v > graf[link][0]:
            graf[link][0:3] = [v, i, prod]

day = hiDay
while day > 0:
    if graf[day][2] > 0:
        print day, ":\t", graf[day][0], products[graf[day][2]]
    day = graf[day][1]