通过交易最大化利润

我一直在这个问题上停留了一段时间，试图找出以下问题的重现关系。通过交易最大化利润

问题描述：

假设在市场以下列商品选项是可能的：

1金属〜2木材
1木至0.2玻璃
1玻璃至1.5金属
1木材0.4火
1火3金属

确定是否有可能通过交易赚取某个项目的利润。

例如，在上面所描述的情况下，我们可以通过以下操作使上金属利润： - > 2木材 - > 0.8火灾 -

1金属> 2.4金属

的部分，其中我被困住的是子问题应该如何分解。对于括号乘法问题，这个问题似乎很熟悉，我们试图通过一系列乘法使最终结果最大化，但有更多的限制。

我不想完整的答案，但提示可以推动我走向正确的方向将非常感激！

谢谢！

来源

2016-03-13 tempNULL

提示：这看起来像一个可以很好地表示为图形的问题。这个图表中的解决方案是什么样的？你能证明，如果有解决方案，那么必须有一个*最小的*这样的解决方案，它有一些特别简单的结构？ –

我会将此作为一个图形问题来处理。每一项都是一个节点，每一个可能的交易都是一个边缘那么什么决定了一个有利可图的交易场景 –

@j_random_hacker谢谢，我会试试看，它似乎更简单的一个图形问题！ – tempNULL

提示：您可以通过“玩”权重并将其减少到已知加权最短路径问题来解决此问题。

扰流：详细说明

这可通过查找在图上的负怀特周期很好地解决了，配重块：

让w'(u,v)是转化的u一个单元的成本到v。定义：

w(u,v) = -log(w'(u,v))

的想法是一个路径v1->v2->...->vk具有

COST = w(v1,v2) + w(v2,v3) + ... + w(vk-1,vk) = 
    = -log(w'(v1,v2)) + -log(w'(v2,v3)) + ... + -log(w'(vk-1,vk)) = 
    = -log (w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk))

成本现在，人们容易看到的w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk)值是完全相同的vk从一个单元所产生的量v1。

同样，对于一些u本身任何周期：u->v1->v2->v3->...vk->v的w'(u,v1)*w'(v1,v2),...,w'(vk,u)值，你可以有多少单位产生这样，该值是大于1，当且仅当-log(w'(u,v1)*w'(v1,v2),...,w'(vk,u) < 0

所以，这问题可以很容易地减少到一个已知的算法 - Bellman-Ford，它可以轻松检测到负循环的存在。

来源

2016-03-13 17:38:44 amit

谢谢！这很有道理！ – tempNULL

通过交易最大化利润

回答

相关问题