Current location - Education and Training Encyclopedia - Graduation thesis - How to prove that the optimal loading problem has greedy selection property
How to prove that the optimal loading problem has greedy selection property
For example, if you take the minimum weight of each loading as a greedy choice, then making the weight from small to large (x 1, x2, ... xn) is the optimal solution of the optimal loading problem. Let k=min{i|xi= 1}. When k= 1, (x 1, x2, ..., xn) is the optimal solution satisfying the greedy property. When k> 1, let y= 1, yk = 0, yi = xi, and i is not equal to k, then the sum of the products of yi and the corresponding weight wi = w 1-wk+wixi is less than or equal to the sum of the products of wi*xi, and less than the capacity c, therefore. But the sum is equal to the sum of changes, that is, (y 1, y2, ..., yn) is also the optimal solution of a complete set of greedy properties. conflict