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 (CO2) 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 CO2 and for other weeks companies B or C might
produce less CO2. Al would like to switch providers each
week to make use of the one that produces the least CO2, but
switching creates extra CO2 (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 CO2 and that, over two weeks, using
company A will cause the release 130 and 77 units of CO2 while
using company B will cause release of 85 and 101 units of CO2.
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, a1, a2,
..., an and b1, b2, ..., bn
and c1, c2, ..., cn, of CO2
amounts over n weeks for companies A, B, and C, respectively. We
also know p, the amount of CO2 released due to changing
providers. Give an algorithm to determine which provider to use
for each week so that total CO2 released is minimized.
(Hint: think Dynamic Programming.)
- Suppose that company A has switched to trucks that burn only
bio-fuels. Now the amount of CO2 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.