hard20 pts · first answer countsdynamic-programminggreedy

Proving a greedy rule is optimal

How is an exchange argument used to prove a greedy algorithm correct?

A.Run greedy on many random inputs and compare with brute forceB.Show that the greedy version runs faster than the DPC.Show that the greedy choice is the only possible choiceD.Show an optimal answer can take the greedy choice and stay optimal

Discussion 0

Join free to post in the discussion.

Proving a greedy rule is optimal

Discussion 0

Related questions