[問題] Reduce LP成Min-cost flow
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間10年前 (2015/01/12 23:27)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/5 (看更多)
在網路上看到一個問題：
給定一個整數陣列 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), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421076460.A.A59.html
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
