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 si of equipment (measured in pounds) that has to be shipped by an air freight carrier. Each weeks 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 si to ship a weeks supply si). Company B makes contracts for a fixed amount c 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 in 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 s1, s2, . . . , sn and returns a schedule of minimum cost. For example, suppose r = 1, c = 10, and the sequence 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, company B for the next block of four contiguous weeks, and then company A for the final three weeks.

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 si of equipment (measured in pounds) that 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 supplys Company B makes contracts for a fixed amount c 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 in 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 s1,82,Sn and returns a schedule of minimum cost. For example, suppose r 1,c 10, and the sequence 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, company B for the next block of four contiguous weeks, and then company A for the final three weeks. 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 si of equipment (measured in pounds) that 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 supplys Company B makes contracts for a fixed amount c 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 in 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 s1,82,Sn and returns a schedule of minimum cost. For example, suppose r 1,c 10, and the sequence 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, company B for the next block of four contiguous weeks, and then company A for the final three weeks