Suppose you are consulting for a company that manufactures PC equipment and ship

Question

Suppose you are consulting for a company that manufactures PC equipment 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 x s to ship a week's supply si). Company B makes contracts for a fixed amount e per week, independent 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 vlues s1,S2,,Sn and returns a schedule of minimum cost. Example. Suppose r = 1, c = 10, and the seqeunce of values is 11,9,9,12,12, 12,12,9,9,11. Then, the optimal schedule would be to choose company A for the first three weeks, then company B for a block of four consecutive weeks, and then company A for the final three weeks.

Explanation / Answer

Solution:

Let "Optimal (i) " be the charge for the best schedule in excess of the weeks "1" to "i".

think what will happen in "ith" week:

Hiring Company-A

We can hire the Company-A for the week "i". It income that we will be paying "r *si" to the Company-A for the week "i".

Also, we have to pay for the preceding weeks. We need to decide the best agenda, thus we will select the optimal agenda over the weeks "1" to "i-1".

This suffer a price of "Optimal (i-1) ".

Therefore, the sum cost of hire Company-A is "r *si + Optimal ( i-1 ) ".

Hiring Company-B

We can employ the Company-B for the week "i". As we be supposed to do this in 3-week blocks, it means we will have to use Company-B in the weeks "i-l" and "i-2" also.

Thus, we need to disburse the Company-B for 3 weeks at the rate "c" per week. i.e., "3c" in total.

Now, we need an optimal agenda over all the previous weeks, in this case, weeks "1" to "i-3". This costs "Optimal ( i-3 ) ".

Therefore, the sum cost of hiring corporation- B is "3c + Optimal (i-3) ".

The cheaper single is the best cost, thus,

Optimal (i)= min ( (r*si + Optimal (i-1) ) (3c + Optimal (i-3) ) )

Recurrence by

dispensation the base for the reappearance is trickier here. The "easy" case is "Optimal (0 ) " = zero.

But come again? about week 1 and week 2?

We have analyzed this from side to side a option tree. It provides 3 cases for the week 1 and week 2.

Case 1: Pick Company-A in both the weeks.

Case 2: Pick Company-A in week 1 and Company - B in week 2.

Case 3: Pick Company-B in both the weeks.

Thus computing smallest amount cost needs computing the reappearance employing each of the 3 possibilities as the bottom cases and opting which give the min result in "Optimal (n)".

Algorithm by

Define 3 arrays. For example, "CostOfAA [ . . . n] ", "Cost0fAB [ 0 . . .n]" and "CostOfBB [0 . . . n] ".

Initialize constituent 0 of each array to "zero".

Initialize element 1 and part 2, according to which case is opted.

Iteratively calculate rudiments 3 to n of every array by the "Optimal (i) " recurrence.

Finally, return the lowest amount of "CostOfAA [ 0 . . . n ]", "Cost0fAB [0 . ..n]" and "CostOfBB [0 . . . n] ".

This algorithm takes O(n) time to figure.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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