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