作者windsfk (風)
看板Programming
標題[問題] 類似Linear programming的問題
時間Wed Jun 3 14:41:17 2015
我現在要處理一個問題
a1 a2 a3 b1 b2 b3 = [17,17,0,28,28,6] , [22,22,11,17,17,0] ..
有6組可挑選(之間沒有關係)
c1 c2 c3 d1 d2 d3 = [6,6,0,22,22,11] , [17,17,0,22,22,0] ..
一樣有6組可選(之間沒有關係)
然後我想求minimize
max(a1,b1,a3,b3,a2+d3,b2+c3,c1,c2,d1,d2)
這樣的問題除了窮舉有比較好的方法嗎?
有人建議我使用ILP(integer linear programming)
但我實在是定不出constrain
有沒有前輩可以給些建議
--
睡前收到女友的簡訊 短短一句「我們分手吧...」
在我還來不及悲傷之前 她又傳了一封給我「對不起我傳錯了...」
比悲傷更悲傷的事
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.73.204
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1433313688.A.6C1.html
1F：推 bxxl: 這不是ILP吧,你的係數又不是連續的整數範圍 118.160.231.76 06/03 17:33
2F：→ MOONRAKER: 才36組，可以了巴 61.221.51.43 06/03 18:03
是這樣子的 這是小CASE
大的CASE會是6的n次方種組合 用窮舉在n大於5可能會有點糟
※ 編輯: windsfk (140.115.73.204), 06/03/2015 19:36:42
3F：推 bxxl: 後來有想到寫成0-1 programming的方式 118.160.231.76 06/03 22:09
4F：→ bxxl: 只是這樣會比較快嗎? 118.160.231.76 06/03 22:12
5F：→ bxxl: 我懷疑0-1 integer programming也是窮舉 118.160.231.76 06/03 22:13
6F：推 qcmi: 乍看之下，應該要全部參數丟進去max函數算過 1.171.152.202 07/19 10:15
7F：→ qcmi: 後，才知道那組最小吧？ 1.171.152.202 07/19 10:15
8F：→ gomi: 沒有consttaint不是很好嗎223.140.148.191 12/14 07:12