Al Gore-ithm has become concerned about global warming and has decided to
modify his energy consumption in order to minimize the amount of carbon
dioxide (CO_{2}) produced. There are three electricity
providers in his area, but all three providers, depending on seasonal
weather and various other factors, change their electricity generating
methods from week-to-week. Thus, for some weeks of the year company A
might produce less CO_{2} and for other weeks companies B or C might
produce less CO_{2}. Al would like to switch providers each
week to make use of the one that produces the least CO_{2}, but
switching creates extra CO_{2} (e.g., the companies have to send
trucks out to his house).
Here's an example using just two companies. Suppose that changing
providers costs 40 units of CO_{2} and that, over two weeks, using
company A will cause the release 130 and 77 units of CO_{2} while
using company B will cause release of 85 and 101 units of CO_{2}.
If we use company B for the first week and then change to company A for the
second week then the total released is 85 + 77 + 40 = 202. If we stay
with company B for the whole two weeks then the total released is 85 + 101 =
186.
- So here's the problem: We have lists, a_{1}, a_{2},
..., a_{n} and b_{1}, b_{2}, ..., b_{n}
and c_{1}, c_{2}, ..., c_{n}, of CO_{2}
amounts over n weeks for companies A, B, and C, respectively. We
also know p, the amount of CO_{2} released due to changing
providers. Give an algorithm to determine which provider to use
for each week so that total CO_{2} released is minimized.
(Hint: think Dynamic Programming.)
- Suppose that company A has switched to trucks that burn only
bio-fuels. Now the amount of CO_{2} released when switching to
company A is reduced (but the switch-over cost remains the same for the
other companies). Briefly explain how your algorithm should be
changed to reflect this new information.