算法 邮箱里的一道题目, 有没有好的算法.
关于排列组合的题目。昨晚用自己的方式已经解决。大家有没有好的算法探讨一下。
You are planning a big programming conference and have received many proposals which have passed the initial screen process but you're having trouble fitting them into the time constraints of the day -- there are so many possibilities! So you write a program to do it for you.
The conference has multiple tracks each of which has a morning and afternoon session.
Each session contains multiple talks.
Morning sessions begin at 9am and must finish before 12 noon, for lunch.
Afternoon sessions begin at 1pm and must finish in time for the networking event.
The networking event can start no earlier than 4:00 and no later than 5:00.
No talk title has numbers in it.
All talk lengths are either in minutes (not hours) or lightning (5 minutes).
Presenters will be very punctual; there needs to be no gap between sessions.
Note that depending on how you choose to complete this problem, your solution may give a different ordering or combination of talks into tracks. This is acceptable; you don’t need to exactly duplicate the sample output given here.
Test input:
Writing Fast Tests Against Enterprise Rails 60min
Overdoing it in Python 45min
Lua for the Masses 30min
Ruby Errors from Mismatched Gem Versions 45min
Common Ruby Errors 45min
Rails for Python Developers lightning
Communicating Over Distance 60min
Accounting-Driven Development 45min
Woah 30min
Sit Down and Write 30min
Pair Programming vs Noise 45min
Rails Magic 60min
Ruby on Rails: Why We Should Move On 60min
Clojure Ate Scala (on my project) 45min
Programming in the Boondocks of Seattle 30min
Ruby vs. Clojure for Back-End Development 30min
Ruby on Rails Legacy App Maintenance 60min
A World Without HackerNews 30min
User Interface CSS in Rails Apps 30min
Test output:
Track 1:
09:00AM Writing Fast Tests Against Enterprise Rails 60min
10:00AM Overdoing it in Python 45min
10:45AM Lua for the Masses 30min
11:15AM Ruby Errors from Mismatched Gem Versions 45min
12:00PM Lunch
01:00PM Ruby on Rails: Why We Should Move On 60min
02:00PM Common Ruby Errors 45min
02:45PM Pair Programming vs Noise 45min
03:30PM Programming in the Boondocks of Seattle 30min
04:00PM Ruby vs. Clojure for Back-End Development 30min
04:30PM User Interface CSS in Rails Apps 30min
05:00PM Networking Event
Track 2:
09:00AM Communicating Over Distance 60min
10:00AM Rails Magic 60min
11:00AM Woah 30min
11:30AM Sit Down and Write 30min
12:00PM Lunch
01:00PM Accounting-Driven Development 45min
01:45PM Clojure Ate Scala (on my project) 45min
02:30PM A World Without HackerNews 30min
03:00PM Ruby on Rails Legacy App Maintenance 60min
04:00PM Rails for Python Developers lightning
05:00PM Networking Event
我的大致思路是：
- 上午 下午分别进行排列组合
- 上午下午的组合拼接在一起
- 把有数据重复的组合剔除掉 这个过程耗时很久。抛砖引玉
这是个最优化问题，可以用 MILP 解决
设 Talk input i 的事件段是从 b_i 开始，时长为 L_i
Lunch 是个特殊事件，可以设 b_0 = 12:00, L_0 = 60min
对于 Networking event, 可以设 4:00 <= b_n <= 5:00
我们还可以引入一系列变量 x_ij, 如果 i 事件后如果紧接是 j 事件，那么 x_ij = 1, 否则 x_ij = 0
那么我们有：
\sigma_{i}{x_ij} = 1
\sigma_{j}{x_ij} = 1
x_ij (b_j - b_i - L_i) >= 0 (*)
b_i >= 9:00
b_i + L_i <= b_n (都在 networking event 前面)
binary x_ij
对于式子 (*), 它是非线性的，怎么办呢？
https://download.aimms.com/aimms/download/manuals/AIMMS3OM_IntegerProgrammingTricks.pdf 里有介绍怎么把它写成线性的
然后把这些约束都放到 solver 求解，如果出现 subtour (事件排成一个圈), 动态添加一个约束，直到最后得出一个解。
上面解决了一天内排日程的问题，如果要排很多天怎么办？可以把第二天的 Lunch 和 Networking 都 +24:00, 然后在两天之间塞进一个 Rest 事件解决。
