Suppose you're consulting for a company that packages fresh seafood on the Oregon coast and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply S(i) of product (measured in pounds), which has to be shipped weekly 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 fi xed rate r per pound, so it costs r S(i) to ship a week's supply S(i)
Company B makes contracts for a fi xed amount c per week, independent of the weight.However, contracts with company B must be made in blocks of fi ve consecutive weeks at a time.
A schedule for the seafood company is a choice of air freight companies (A or B) for each of the n weeks, with the restriction that if company B is chosen, it is used for fi ve weeks in a row. The cost of a schedule is the sum of the costs, as described above, paid out over the n weeks.
Give a dynamic programming solution to the problem of determining the minimum possible cost of a schedule, given inputs s1; s2....... Sn, r, and c.