Dinkelbach算法 实例

前言

关于01规划不用说太多了。大致介绍和例题都在上一篇文章[POJ2976]Dropping tests里。这篇大致给大家介绍一下Dinkelbach算法。

 

大致介绍

跟二分答案法一样的是,在算出一个解的时候,都是用了贪心法来构造出一组解,唯一不同的是逼近更优解的方法。二分法是利用答案的单调性,而Dinkelbach算法用的是迭代。
Dinkelbach算法在用一个 R 做好贪心的准备后,用这组解算出一个新的 R' 并以此迭代。
这种方法比二分答案快,但是精度并没有二分答案高。
具体可以看代码:

 

代码

 

完结

One thought on “Dinkelbach算法 实例

发表评论

电子邮件地址不会被公开。 必填项已用*标注