Data Structures, Algorithms, & Applications in C++
Chapter 19, Exercise 19

  1. If component i has a supplier k whose product has weight and cost greater than or equal to that of the product from supplier q, then supplier k may be eliminated for this component because there is no advantage to using this supplier over supplier q.

  2. Relabel the suppliers that remain for each component so that the first supplier has least cost (and hence maximum weight) and the last supplier has maximum cost (and hence least weight). Notice that following the elimination of item (1), two suppliers cannot provide the same component with the same weight or the same cost.

  3. We obtain the following dynamic programming equations:

    If component 1 has one supplier remaining, then
    w(1,j) = infinity, j < C1,1
    w(1,j) = W1,1, C1,1 <= j <= c
    If component 1 has two suppliers remaining, then
    w(1,j) = infinity, j < C1,1
    w(1,j) = W1,1, C1,1 <= j < C1,2
    w(1,j) = W1,2, C1,2 <= j <= c
    If component 1 has three suppliers remaining, then
    w(1,j) = infinity, j < C1,1
    w(1,j) = W1,1, C1,1 <= j < C1,2
    w(1,j) = W1,2, C1,2 <= j < C1,3
    w(1,j) = W1,3, C1,3 <= j <= c


    and

    If component i, 1 < i <= n, has one supplier remaining, then
    w(i,j) = infinity, j < Ci,1
    w(i,j) = Wi,1 + w(i-1, j-Ci,1), Ci,1 <= j <= c

    If component i, 1 < i <= n, has two suppliers remaining, then
    w(i,j) = infinity, j < Ci,1
    w(i,j) = Wi,1 + w(i-1, j-Ci,1), Ci,1 <= j < Ci,2
    w(i,j) = min{Wi,1 + w(i-1, j-Ci,1), Wi,2 + w(i-1, j-Ci,2)}, Ci,2 <= j <= c

    If component i, 1 < i <= n, has three suppliers remaining, then
    w(i,j) = infinity, j < Ci,1
    w(i,j) = Wi,1 + w(i-1, j-Ci,1), Ci,1 <= j < Ci,2
    w(i,j) = min{Wi,1 + w(i-1, j-Ci,1), Wi,2 + w(i-1, j-Ci,2)}, Ci,2 <= j < Ci,3
    w(i,j) = min{Wi,1 + w(i-1, j-Ci,1), Wi,2 + w(i-1, j-Ci,2), Wi,3 + w(i-1, j-Ci,3)}, Ci,3<=j<=c



We may determine the supplier for each component as follows:
Step 1
Eliminate suppliers as in item 1 above and relabel suppliers as in item 2. This takes O(n) time.
Step 2
Compute w(1,j) for 0 <= j <= c using the equation for w(1,j) obtained in item 3 above. This takes O(c) time.
Step 3
Compute w(i,j) for i = 2, ..., n, in that order, using the equation for w(i,j) developed in item 3 above. For each i, compute w(i,j) for 0 <= j <= c (this can be done in any order). It takes O(cn) time to compute all of these w(i,j) values.
Step 4
w(n,c) gives the least weight machine that can be constructed at a cost that does not exceed c. The supplier for each component is determined by using a traceback procedure for w(n,c). Assume that w(n,c) != infinity. Therefore, it is possible to build the machine at a cost that does not exceed c.

The traceback for w(i,j) is recursive. When i = 1, there are three cases to consider. If w(1,j) = W1,1, get component 1 from supplier 1, if w(1,j) = W1,2, get component 1 from supplier 2; otherwise, get component 1 from supplier 3.

When i > 1, there are also three cases to consider. If w(i,j) = Wi,1 + w(i-1, j-Ci,1), then get component i from supplier 1 and do a traceback for w(i-1, j-Wi,1) to determine the suppliers for the remaining components; if w(i,j) = Wi,2 + w(i-1, j-Ci,2), then get component i from supplier 2 and do a traceback for w(i-1, j-Wi,2) to determine the suppliers for the remaining components; otherwise, get component i from supplier 3 and do a traceback for w(i-1, j-Wi,3) to determine the suppliers for the remaining components. The traceback takes O(n) time.


From the above description and analysis, we see that the overall complexity is O(cn).