[问题] 基于排序的greedy

楼主: wsx02   2014-04-01 21:38:23
有一个问题是
给定n个index(x,y,z)
因为不太擅长描述 所以想用例子说明
假如n=5
a( 1, 2, 5)
b( 8,10,14)
c( 4, 7,10)
d( 7, 6, 8)
e( 2, 8, 7)
则要output:
a( 1, 2, 5)
d( 7, 6, 8)
b( 8,10,14)
因为 a < d < b 这边是用(x,y,z)去比较
有点像是前面的东西可以被后面的东西覆蓋住
假如我先针对x由小大到排序 然后再把符合条件的index加入
这样有一个问题是
a( 1,10, 1)
b( 2, 2, 2)
c( 3, 3, 3)
d( 4, 4, 4)
这样的方法只会找出a
但是最佳的是b,c,d
我是知道用greedy的方式不一定能找出最佳解
可是假如希望用greedy的方式能够找出比较好的解
请问有比较好的方法可以达成吗?
或是请问这题如果要用DP去解
应该怎么切割成subproblem呢?
是否也需要先针对x,y,z其中一个先进行排序呢?
谢谢
作者: flere (人间失格)   2014-04-01 21:47:00
DP的话可以查查LIS的作法~
作者: isnoneval (虚物之海)   2014-04-03 19:10:00
针对 x,y,z 的字典顺序排一遍再从小到大扫一遍, 遇到 y 或 z 逆序就断开, 记住最长链

Links booklink

Contact Us: admin [ a t ] ucptt.com