PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Reduce LP成Min-cost flow

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (口德是一種美德)時間10年前 (2015/01/13 00:39)推噓5(5推 0噓 3→)

留言8則, 2人參與討論串2/5 (看更多)

竟然會有 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://www.ptt.cc/bbs/Prob_Solve/M.1421080782.A.F9F.html

推

FRAXIS

01/13 00:45, , 1^F

01/13 00:45, 1^F

→

FRAXIS

01/13 00:45, , 2^F

01/13 00:45, 2^F

推

FRAXIS

01/13 00:46, , 3^F

01/13 00:46, 3^F

Bingo！ (這.......你......) 其實一看到最X化，以往經驗幾乎是Dynamic Programming。但是如加上performance限制的話，我能攤手嗎(笑)？在開寫之前還是先google一下好了。 careercup.com印象中還有知名企業即時聊天功能的樣子。 ※ 編輯: bleed1979 (220.135.203.156), 01/13/2015 00:56:30