Algorithm Design for Linear Programming

I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing.

I am working on the following problem:

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_i$$ 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$$ x $$s$$ to ship a week's supply $$s_i$$).

• 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 $$s_1, s_2, \cdots, s_n$$ 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.

I am trying to write algorithm, in pseudo code, that completed the following steps in order to solve the challenge, but I don't know even where begin this solution. My initial suspect on how to solve this:

• Determine what the "optimal" formula looks like, which is: MIN((r*s + OPT(i-1), (3c + OPT(i-3))

This would determine the most optimal between $$A$$ or $$B$$ given their restrictions. Therefore I would need to determine the most optimal schedules for the weeks preceding the $$i^{\text{th}}$$ week. Meaning I would end up running OPT(n-1) for every n, thus resulting in OPT(n) total runs so (n) time complexity.

Any advice on how to generate pseudocode for this would be appreciated...I am trying to learn but am not very effective.

• Could you please credit the original source of the problem? Nov 20 '18 at 12:05
• I don't know what the source is, it was a handout in class @Apass.Jack Nov 27 '18 at 1:36

The approach you used is called dynamic programming.

In dynamic programming, a series of decisions are made in order to maximize some function, where the options available at any given time depend on the decision we have made before. You may want to check a tutorial on TopCoder or some course material at your hand.

You have started to figure out the recurrence relation, the hallmark of dynamic programming. However, it looks like you made an off-by-one error.

You can imitate the pseudocode in that tutorial. Or many other pseudocode such as those in the Introduction to algorithm by Corman et al.

Here is my pseudocode for this problem, where you can find the correct recurrence relation. I assume $$n\ge4$$; otherwise the only choice is to use company $$A$$ always.

1. Let $$OPT$$ be an array of size $$n$$.
2. $$OPT=0$$, $$OPT=s_1r$$, $$OPT=(s_1+s_2)r$$, $$OPT=(s_1+s_2+s_3)r$$
3. For $$i$$ = 4 to $$n$$, $$OPT[i] = \min(OPT[i-1] + s_ir, OPT[i-4] + 4c)$$
4. Output $$OPT[n]$$
• Thank you, this confirmed what I was thinking. Nov 27 '18 at 1:37