给定一组具有关联权重的活动，选择一组将使总权重最大化的不重叠活动集。
给定一组具有关联权重的活动，选择一组将使总权重最大化的不重叠活动集。
提问于 2016-11-19 14:48:40
我一直在思考和寻找这个问题的解决方案，在维基百科上找到了这个。
该解决方案建议为i查找带有完成时间<=启动时间的活动。但是，请考虑以下示例：
启动时间:1，2，3，4，5
结束-时间:3，4，5，6，7
分别-重量:13，5，2，4，1
在这个例子中，当我在活动：(4-6)时，我将有两个活动，其结束时间小于4，所以，与其通过二进制搜索搜索一个数字，我们不应该返回一个数组，然后从数组中获取最大值。
如果我误解了这个概念，请纠正我。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-11-19 14:55:51
根据这篇文章，opt[i] = MAX(opt[i-1], opt[t] + w(i))，也就是说，opt[i]考虑到了i-th之前结束的所有活动。这就是为什么不需要迭代所有可能的选项。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40694198
复制相关文章
相似问题
腾讯云开发者
