Find an instance that forces the Engineers method to have as large a performace

Question

Find an instance that forces the Engineers method to have as large a performace retion as possible. It is possible to get 1.16... but not much higher.

Number Partitioning (+ Extra Credit) Number Partitioning Problem: Given a set of POSITIVE INTEGERS, divide it into two piles, such that the sums of numbers in each pile differ by as little as possible How would you solve this? The "Engineer's Method" for Number Partitioning: Sort the numbers from largest to smallest. Beginning with the largest number, put each successive number into the pile that has smaller sum. Performance Ratio: For a given instance (set of numbers) S of Number Partitioning, the performance ratio of the Engineer's Method (EM) is (sum of #'s in larger EM pile) / (min possible sum of #'s in larger pile) Extra Credit: Find an instance that forces the Engineer's Method to have as large a performance ratio as possible.

Explanation / Answer

1) let's sort the stones descending.

2) i=1

3) A is the index of the lightest sack (or first if they have equal weight)

4) put m[i] stone to S[A], S[A] += m[i]

5) i++

6) if there are stones left (i <= n) then goto 3

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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