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