Exercises 323 In your example, say what the correct answer is and also what the

Question

Exercises 323 In your example, say what the correct answer is and also what the algorithm above finds (b) Give an efficient algorithm that takes values for aj,a2, ..., an and , bn and returns the value of an optimal plan. bi, b2, 11. Suppose you're consulting for a company that manufactures PC equip- ment and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply s, of equipment (measured in pounds), which has to be shipped by an air freight carrier. Each week's supply can be carried by one of two air freight companies, A or B ·Company A charges a fixed rate r per pound (so it costs r·s, to ship a week's supply s,) * Company B makes contracts for a fixed amount c per week, indepen- dent of the weight. However, contracts with company B must be made in blocks of four consecutive weeks at a time. A schedule, for the PC company, is a choice of air freight company (A or B) for each of the n weeks, with the restriction that company B, whenever it is chosen, must be chosen for blocks of four contiguous weeks at a time. The cost of the schedule is the total amount paid to company A and B, according to the description above Give a polynomial-time algorithm that takes a sequence of supply values si, s2, . . . , Sn and returns a schedule of minimum cost. Example. Suppose r= 1, c= 10, and the sequence of values is

Explanation / Answer

A) The above algorithm will fail when the pattern will be as follows:

Since it considers only two values(first and second), the job will never be able to execute on Machine B.

Incorrect answer : 55

Correct answer : 89

To consider the above into the algorithm, the modified version of the variable is:

In Minute 1, choose the machine having larger of a1, b1

Set i = 2

while i <= n

what was the choice in minute i-1

IF A:

If B(i+1) + B(i+2) > A(i) + A(i+1) + A(i+2)

Choose move in minute i and B in minute i+1 and i+2.

Proceed to iteration i+3.

ELSE:

Choose A in minute i.

Proceed to iteration i+1.

ELSE IF B:

swap A and B with same behaviour

A B 10 5 5 14 10 14 5 14 10 14 5 14 10 14

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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