作者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/m.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