Suppose you’ve been sent back in time and have arrived at the scene of anancient
ID: 3832337 • Letter: S
Question
Suppose you’ve been sent back in time and have arrived at the scene of anancient Roman battle. Moreover, suppose you have just learned that it is your job to assign n spears to n Roman soldiers, so that each man has a spear. You observe that the men and spears are of various heights, and you have been told (in Latin) that the army is at its best if you can minimize the total difference in heights between each man and his spear. That is, if the ith man has height mi and his spear has height si, then you want to minimize the sum, i=1 to n, |mi si|. Consider a greedy strategy of repeatedly matching the man and spear that minimizes the difference in heights between these two. Prove or disprove that this greedy strategy results in the optimal assignment of spears to men.
Explanation / Answer
Before assigning the spears to soldiers, sort spears in acending order in size and soldiers in acending order of hight.
Assign the smalest spear to shortest soldier. so that difference between heights of soldier and spear will be minimum. Hence the sum of differences will be minimum.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.