3

问题在这里：http ://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2384

我设法使用贪婪的方法解决了这个问题。我将早上的路线按降序排列，晚上的路线按升序排列，然后我将早上路线的最大值与晚上路线的最小值放在一起。该解决方案被接受。我试图证明这个问题具有贪心选择属性，即贪心选择是最优解的一部分。有人可以帮忙证明一下吗。我做这个证明只是为了练习

4

1 回答 1

1

http://mathcentral.uregina.ca/mp/archives/previous2003/nov03sol.html

于 2012-01-27T17:41:50.780 回答