```Circuit Reliability Design as a dynamic programming problem
by Tony C. Smith
--------------------------------------------------------------------

The simplest form of a multi-stage circuit (i.e. a circuit where all
stages are connected in series) is where each stage has one device.
If d_i is the i-th device, and the reliability of d_i is r_i and the
cost of one d_i is c_i, then an n-stage circuit must have

(minimum cost) C_min = SUM_(1<=i<=n) c_i

and its reliability is equal to the probability that any one device
fails, which is

(circuit reliability) RR_n = PROD_(1<=i<=n) r_i

Each stage can be made more reliable by adding copies of the device in
parallel, such that if any one device in that stage fails there is
another to fulfill the function.  Now the reliability of that stage
(sr_i) is equal to the probability that all copies of the device fail
simultaneously, which is

(stage reliability) sr_i = 1 - (1-r_i)^m_i

where m_i is the number of devices in the stage.  Obviously the
circuit reliability computed as

R_n = PROD_(1<=i<=n) sr_i

The goal now is to maximize R_n subject to the constraint of some
budget C (that is, the maximum allowed cost).

The number of additional devices that can be added to any one stage is
at most equal to

u_i = 1 + (int)[(C - C_min)/c_i]

That is, u_i is an upperbound for m_i.  The goal in solving the
circuit reliability problem is to find the set {m_1, m_2, ... m_n}
that maximizes R_n given C.

A dynamic programming solution is possible because the principle of
optimality holds.  As in the knapsack problem, when the decision is
the solution is comprised of the best solution found so far for either
1) the same budget with one-fewer device types to consider, or 2) a budget
with enough money left over to buy one more of the currently available
device types.

If there are i device types available, then S_i,j is the set of
decisions available to us when we can have m_i = j.  That set only
includes decisions that are still viable (i.e. haven't been ruled out
because of available options) after considering i types of devices.
Thus the solution for S_i,j is going to be either the best one found
for S_(i-1), or S_i,j-1 plus one more device of type d_i if we can
afford it.  Put another way, we start considering all 1<=j<=u_1, m_1=j
for {m_1,m_2=1,....,m_n=1} before considering options for m_2.

```