如何证明最优装载问题具有贪婪选择性质

比如你把每次装载的最小重量作为一个贪婪的选择，那么让重量从小到大(x1，x2，...xn)是最优装载问题的最优解。设k=min{i|xi=1}。当k=1时，(x1，x2，...，xn)是满足贪婪性质的最优解。当k & gt1，设y=1，yk = 0，yi = xi，I不等于k，则yi与对应权重wi的乘积之和= w 1-wk+wixi的乘积之和，小于或等于wi*xi的乘积之和，小于容量c，因此，(y65438+。但之和等于易之和，即(y1，y2，...，yn)也是全套贪婪性质的最优解。矛盾