[問題] 類似Linear programming的問題

[windsfk (風)]

我現在要處理一個問題

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://www.ptt.cc/bbs/Programming/M.1433313688.A.6C1.html
推 bxxl: 這不是ILP吧,你的係數又不是連續的整數範圍
→ MOONRAKER: 才36組，可以了巴
是這樣子的  這是小CASE
大的CASE會是6的n次方種組合  用窮舉在n大於5可能會有點糟
※ 編輯: windsfk (140.115.73.204), 06/03/2015 19:36:42
推 bxxl: 後來有想到寫成0-1 programming的方式
→ bxxl: 只是這樣會比較快嗎?
→ bxxl: 我懷疑0-1 integer programming也是窮舉
推 qcmi: 乍看之下，應該要全部參數丟進去max函數算過
→ qcmi: 後，才知道那組最小吧？
→ gomi: 沒有consttaint不是很好嗎