This problem comes from Example 1 - 2. The boat can be loaded step by step, each step is installed, and it is necessary to consider which container is loaded. According to this idea, you can use the following greedy guidelines: from the remaining containers, choose the minimal cargo box. This selection can ensure that the total weight of the selected container is minimized, so that more container can be loaded. According to this greedy, first select the lightest cargo box, then select the light suitcase, so go until all the containers are installed on the boat or boat can no longer accommodate any other container.
Example 1-7 Assume N = 8, [W1, ... W8] = [100, 200, 50, 90, 150, 50, 20, 80], C = 4 0 0. When using a greedy algorithm, the sequence of the trunk is 7, 3, 6, 8, 4, 1, 5, 2. The total weight of the container 7, 3, 6, 8, 4, 1 is 3 90 units and has been loaded, and the remaining load capacity is 1 0 units, less than any of the following containers. In this greeddess solution algorithm, [X1, ..., X8] = [1, 0, 1, 1, 0, 1, 1, 1] and? Xi = 6.
Theorem 1-1 can produce optimal loading using a greedy algorithm.
The prove can be used to prove the optimality of the greedy algorithm: order x = [x1, ..., xn] is the solution obtained with greedy algorithms, order Y = [Y1, ..., yn] is any one. Solution, just prove N? I = 1Xi ≥n? I = 1yi. If you don't lose general, you can assume that the boxes are ranked: 即 wi ≤ Wi 1 (1 ≤ N). Separately turn Y to X, each step in each step is generated in each step, and n? I = 1yi is equal to or equal to the value before the transformation, and finally prove N? I = 1Xi ≥n? J = 1yi.
According to the working process of the greedy algorithm, it is understood that there is a K in the range of [0, n], so that Xi = 1, i ≤ K and XI = 0, I> K. Look for the smallest integer J in the range of [1, n], make XJ ≠ YJ. If there is no such j, n? I = 1Xi = n? I = 1yi. If there is such a, J ≤ K, otherwise Y is not a can solve because xj ≠ yj, xj = 1 and yj = 0. Let YJ = 1, if the result obtained Y is not a feasible solution, there will be one L in the [J 1, N] range to make YL = 1. Let YL = 0, due to WJ ≤ WL, the obtained Y is feasible. Moreover, the resulting new Y has the same number of objects with the original Y.
After several this conversion, Y is converted to x. Since the new Y, the new Y produced at least has the same number of objects as the previous Y, the X has the same number 1 with the initial Y. The C code implementation of the container load algorithm is shown 1 3 - 1. Since the greedy algorithm is loaded by the order of the goods, the program 1 3 - 1 first uses the indirect address sorting function I ndirect s ORT to sort the weight of the cargo box (see 3. 5 Intrinsic integer address), then the container It can be loaded in the order of increments in weight. Due to indirect addressing sort required for O (NL O GN) (also available 9.5. 1 of the heap sorting of chapter 2), the rest of the algorithm is O (N), Therefore, the total complexity of the procedure 1 3 - 1 is O (NL O GN).
Program 13-1 container ship
Template
Void ContainerLoading (int X [], t w [], t c, int N)
{// greedy algorithm for container shipping problems
// x [i] = 1 When and only the container I is loaded, 1 <= i <= n
// c is the capacity of the ship, and W is the weight of the cargo box.
/ / Sort by indirect addressing
// t is an indirect address table
INT * T = New Int [n 1];
I n d I r e c t s o R t (W, t, n);
/ / At this time, W [T [I]] <= W [T [i 1]], 1 <= i
// Initialization X
For (INT i = 1; i <= n; i )
X [i] = 0;
/ / Select items in the order of weight
For (i = 1; i <= n && w [t [i]] <= c; i ) {
X [T [I]] = 1;
C - = w [t [i]];} // remaining capacity
delete [] t;
}
Reprinted from Shada Studio
