作者bleed1979 (口德是一种美德)
站内Prob_Solve
标题Re: [问题] Reduce LP成Min-cost flow
时间Tue Jan 13 00:39:39 2015
竟然会有 FRAXIS 也纳闷求解的问题？！
这引起了我的注意。
完全不想点击连结：因为我相信 FRAXIS 有看懂问题且叙述为真。
而我也看仔细了中文问题描述。
那麽，我就在不使用 Linear Programming、网路流 这两类演算法的限制下，
此时刻开始进行解题，用自己的方法(其实我是有想到应该使用那一种演算法)。
解题的进行时间只到天亮吃早餐前(约6:00 am)。
不论解出与否，都会回来编辑此文回报结果。
※ 引述《FRAXIS (喔喔)》之铭言：
: 在网路上看到一个问题：
: 给定一个整数阵列 A ，一个正整数D，要求设计一个演算法把
: A 修改成 B （长度不变），使得 B 中相邻的元素的差值都小於D，
: 且最小化 |A[i] - B[i]| 的总和。
: http://www.careercup.com/question?id=5207197178920960
: 我自己想的解法是使用Linear programming，但是我又感觉这
: 问题似乎是可以用Min-cost flow来解的，只是我找不出来怎麽作。
: 不知道有没有人有其他解法？
: 考虑一般性的情况，给定一个LP的 formulation ，有没有什麽
: 技巧，在某些条件满足的状况下，可以把LP转成Min-cost flow？
: 因为我觉得设计LP比想出network flow的模型容易许多。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.135.203.156
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1421080782.A.F9F.html
1F：推 FRAXIS: 其实我是想问min-cost flow的解法.. 01/13 00:45
2F：→ FRAXIS: 不过如果有更直觉的解法也挺好的.. 01/13 00:45
3F：推 FRAXIS: 连结里面有很多解法 都是DP 不过都不是多项式时间.. 01/13 00:46
Bingo！ (这.......你......)
其实一看到最X化，以往经验几乎是Dynamic Programming。
但是如加上performance限制的话，我能摊手吗(笑)？
在开写之前还是先google一下好了。
careercup.com印象中还有知名企业即时聊天功能的样子。
※ 编辑: bleed1979 (220.135.203.156), 01/13/2015 00:56:30
5F：→ FRAXIS: 第八页的地方似乎就是这题..只是我看不懂他的解法.. 01/13 01:55
6F：推 dreamoon: 真是巧妙的题目... 01/13 13:43
7F：→ dreamoon: 有上下界的最小花费网路流 01/13 13:44
8F：推 dreamoon: 是说我可不觉得任何LP都可以换成min-cost flow @@ 01/13 13:47