f***g
发帖数: 214 | 1 找到一个Paper
http://arxiv.org/abs/0809.0400v1
也就是看了个稀里糊涂，希望可以帮到其他人。
如果能看的透彻，也麻烦给我们普及一下 |
h**k
发帖数: 3368 | 2 不用搞这么细，你把那个DP的解法吃透就行。那篇文章是研究这个NP问题的近似解法，
并指出什么条件下这个近似解法是最优解。这个只有专门研究算法的才关心。面试没有
人会问这个。
【在 f***g 的大作中提到】
: 找到一个Paper
: http://arxiv.org/abs/0809.0400v1
: 也就是看了个稀里糊涂，希望可以帮到其他人。
: 如果能看的透彻，也麻烦给我们普及一下
|
f***g
发帖数: 214 | 3 假设--
面试时，给了一组面值，
怎么判断优先用什么算法呢 |
h**k
发帖数: 3368 | 4 DP。没有面试官会接受greedy算法的。
【在 f***g 的大作中提到】
: 假设--
: 面试时，给了一组面值，
: 怎么判断优先用什么算法呢
|
h**6
发帖数: 4160 | 5 如果在最大面值的两倍以内，DP和greedy解都是一样的，那么对于所有的数额，DP和
greedy解都是相同的。 |
f****g
发帖数: 313 | 6 The greedy algorithm can be used only if the local optimal can lead to the
global optimal. |
f***g
发帖数: 214 | 7 嗯，有道理...
【在 h**k 的大作中提到】
: DP。没有面试官会接受greedy算法的。
|
