比如所你是按每次装入重量最小的作为贪心的选择，那么设重量从小到大（x1,x2,...,xn）是最优装载问题的一个最优解。设k=min{i|xi=1}.当k=1的时候（x1,x2,...,xn）是一个满足贪心性质的最优解。当k>1，令y=1，yk=0,yi=xi,i不等于k，那么yi与对应重量wi的乘积的和=w1-wk+wixi乘积的和，这个是小于等于本身wi*xi乘积的和的，小于容量c因此，（y1,y2,...,yn）也是最优装载问题的可行解。然而，xi的和与yi的和是相等的，也就是说，（y1,y2,...,yn）也是满组贪心性质的最优解。矛盾。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024