集合覆盖Prob的变化(可能是活动选择Prob)
提问于 2014-12-26 01:31:31
每天早上9点到下午5点，我应该有至少一个人在工厂里监督工人，并确保没有出问题。
目前这份工作有n个申请人，他们每一个人都可以不时地工作，i= 1，2，…，n。
我的目标是尽量减少两个以上的人同时监视工人的时间。
(申请人的工作时间为上午九时至下午五时。)
我已经证明了最多需要两个人来满足我的需求，但是我应该如何从这里得到最终的解决方案呢？
找出只有一个人能胜任这份工作的时间段是我的第一步，但找到下一步是困扰我的.。
该算法必须在多项式时间内运行.
有什么提示(可能是某种类型的数据结构？)或推荐人是欢迎的。非常感谢。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-12-26 02:21:21
我认为您可以通过解决子问题来实现动态规划：
考虑到申请人本人是最后一名工人，我们从一天开始一直覆盖到ci，最低重叠时间是多少？
将此值称为最小重叠时间成本(I)。
您可以通过考虑情况来计算成本(I)的值：
- 如果si等于一天的开始，那么成本(I)=0(不需要重叠)
- 否则，考虑所有以前的申请者j.设置成本(I)到最小的成本(J)+i和j之间的重叠。还将prev(i)设置为达到最小值的j的值。
然后，用k的所有值的最小成本(K)给出你的问题的答案，其中ck等于一天的结束。您可以通过使用prev的值进行回溯来计算出正确的人员选择。
这给出了一个O(n^2)算法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27655256
复制相关文章
![如何找到spring的官方文档[通俗易懂]](https://ask.qcloudimg.com/http-save/yehe-8223537/a7ae5d0806d1dbf97f1ed786bf38d92b.png)
点击加载更多
腾讯云开发者
