#2 rock3334280@2009-07-11 04:08:00
12291
回复
删除
我也是突发奇想
话说要严格证明一个贪心策略的话
是不是需要借助“矩阵胚”还是叫“拟阵”的模型？
顺便问一下 有所耳闻 小菜我只是知道这两个名词而已
#3 rock3334280@2009-07-11 06:26:00
12301
回复
删除
我在oibh上找到的 对不对 请大牛们指教：
“对于这个题，贪心算法也是可以的。随着论文的增加，耗费的时间将呈指数级增长，使得时间越来越多。我们可以算出对于每个课题，新添第x篇论文需要增加多少时间（Ai*x^Bi-Ai*(x-1)^Bi）。每一次选择论文的课题时，都选择增加时间最少的课题。对 于这个贪心，我们可以简单证明如下：如果这次不选择增加最小时间的课题，那么若以后永远不选，则这次改选成它将更优；若留着以后选，则这次选了没有影响， 不会更差。这个贪心的策略必须要基于这个事实：随着每个课题已有论文的数目的增加，新增一篇文章需要多花费的时间将越来越多。”