在下面的封面实例中。贪心算法会选择多少组？所有套装的成本为 1。
谁能给我解释一下。这个问题的解决方案是什么。
那么贪心算法将如何适用于第二个实例。
它在实例中选择了多少组。
问问题
505 次
1 回答
2
考虑到贪心算法每次都会选择最好的集合，如果它是由每个集合中的点数决定的，那么它首先会取最大的。
取一个后，它将从其余集合中删除重叠的点，然后再次选择最大的点。所以剩下的集合看起来像：
因此折叠顺序应该是3套：
这是一个很好的问题，它说明了它是如何没有达到最佳性能的，因为有可能只用 2 组来解决这个问题。你可以在这里阅读更多内容：http: //pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture02.pdf
于 2017-02-08T10:22:15.173 回答