Greedy Algorithm Basic idea 1 CRE 3U Match all triples when it is possible The total utility score is 18+20+ 12=50 Match Utility Score 18 @ (t2p1,w1) 90 (t1,p1,W2) 10 (t2,p1,Ww2) 20 20 20 12 48 4P3 72⚫ Basic idea ⚫ Match all triples when it is possible. Greedy Algorithm 𝑡1 𝑡2 𝑡3 𝑡4 𝑝1 𝑝2 𝑝3 𝑤3 𝑤1 𝑤2 Match Utility Score (𝑡1 ,𝑝1 , 𝑤1 ) 18 (𝑡2 ,𝑝1 , 𝑤1 ) 90 (𝑡1 ,𝑝1 , 𝑤2 ) 10 (𝑡2 ,𝑝1 , 𝑤2 ) 20 (𝑡2 ,𝑝2 ,𝑤2 ) 20 (𝑡2 ,𝑝2 ,𝑤3 ) 20 (𝑡3 ,𝑝2 ,𝑤2 ) 12 (𝑡3 ,𝑝2 ,𝑤3 ) 48 (𝑡4 ,𝑝3 ,𝑤2 ) 72 (𝑡4 ,𝑝3 ,𝑤3 ) 12 CR= 1 3𝑈𝑚𝑎𝑥 The total utility score is 18+20+12=50 42