Dav*_*ang 15 algorithm dynamic-programming
问题是这样的(翻译):
在山脚下有n(n <= 25000)人,每个人都想上山,然后下山.有2个导游:一个用于帮助一个人上山,一个用于帮助一个人下山.我占用(i)时间爬上这座山,然后下来(i)下降它的时间.但是,每个导游一次只能帮助1个人(这意味着最多可以攀爬1个人,并且在任何给定时间最多可以有1个人下山).假设当"向上"指南到达顶部时,他立即被传送回底部,就像"向下"指南一样.找到让每个人上下山的最短时间.(必要时,人们可以聚集在山顶)
这是问题的示例输入,由我注释:
3 persons
person 1: up=6 minutes, down=4 minutes
person 2: up=8 minutes, down=1 minutes
person 3: up=2 minutes, down=3 minutes
输出到输入:
最小时间是17.这是因为如果第3个人先行,然后是人1,然后是人2(并且同样的顺序用于上升和下降),则总时间为17.
我已经尝试了一些算法,但这是我到目前为止所拥有的:
一个O(n!*n)算法:使用next_permutation将奶牛通过所有可能的排列进行置换
一个贪婪的算法:我通过减少下降时间对人们进行排序,并尝试将它们放在一起,但这并没有产生正确的解决方案.
其他想法
我现在转向动态编程,因为根据CLR,优化问题通常是贪婪或动态编程(我认为这个问题满足最佳子结构).
我注意到,在最小的解决方案中,"向上"指南将不会休息,直到每个人都上山.(所以人1的上升,人2的上升等之间没有差距.)也许问题可以减少到只是最小化下降时间之间的差距？
我无法想象这个动态编程问题的状态,(我不认为它是单维的,因为我不认为你能找到最适合i-1人的最佳解决方案的解决方案) .
有人可以帮忙吗？