有一個問題是
給定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其中一個先進行排序呢?
謝謝