Dynamic Programming The year is 2050, and you\'re the manager for Bone Apple Tea

Question

Dynamic Programming

The year is 2050, and you're the manager for Bone Apple Tea, CWRU's only dining service left operating after the start of this year's HvZ. You have been asked by Babs to distribute rations to maximize the number of students who survive. Luckily, you have exactly as many packs of rations as there are students, but your entire kitchen has been zombified and the packs of rations are of wildly varying caloric values. Suppose that you have a list C-(ci, ..., Cn) of the calorie counts of the rations, and a list B (bi, .., bn) of the benefits4 per calorie toward survivability of each student 5. A pairing of students with rations is an assignment of one and only one ration° to each student, represented as a list of pairs of the form (i, j) where i represents the index of a ration in the list of rations, and j represents the index of the student it was assigned to in the list of the students' benefits per calorie. Give an algorithm to pair students and rations so as to maximize the total benefit toward survivability, and prove its correctness. (**)

Explanation / Answer

ALGORITHM:

We have two lists C := { c1 , c2 , c3 , ... , ci , ... , cn }

and B := { b1 , b2 , b3 , ... , bi , ... , bn }

Sort C and B in increasing order.

The sum of product P = c1*b1 + c2*b2 + ... + ci*bi + ... + cn*bn

is now the maximum.

WHY IT WORKS:

Let us take p, q, r and s such that

Let p < q and r < s

then we have (pr + qs)

// this is according to our algorithm

// multiplying larger values together

and we have (ps + qr)

//this is the other possiblity

(pr + qs) - (ps + qr) = (q-p)(s-r) > 0

Therefore, (pr + qs) > (ps + qr)

Now if we have paired 2 elements from C and two elements from B

then greater valued element of C and B multiplied together and smaller valued multiply together will give a greater sum.

This can be generalised to n values of C and B.

Also known as Rearrangement inequality

PROOF OF CORRECTNESS:

Our algorithm is correct as it pairs the greatest terms of C and B together, followed by second greatest term and so on.

By above discussion(WHY IT WORKS) it is correct.

TIME COMPLEXITY:

Sorting arrays take O(nlogn) time, therefore overall time complexity is O(nlogn){n is size of array};

EXAMPLE:

{1,2,3} and {4,5,6}
3*6 + 2*5 + 1*4 = 32

if we exchange any values, the sum decreases
2*6 + 3*5 + 1*4 = 31

the minimum sum comes when we reverse our algorithm
1*6 + 2*5 + 3*4 = 28

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.