❶ 哪位高手能說說證明貪心選擇性質的一般方法呢謝謝~
比如首先按物品的重量從小到大排序。貪心選擇性質說的就是每次都是都是選取當前的最優值。假設背包問題每次都是從重量最小的物品開始選擇的，那他一定滿足貪心選擇性質，假設背包問題不是從重量最小的物品開始選擇的，那麼說明重量最小的物品沒有裝入，現在我們用這個重量最小的物品代替當前選擇裝入的物品，依然可以得到一個最優解（裝入的物品的個數相同）。所以背包問題具有貪心選擇性質。
❷ 如何證明最優裝載問題具有貪心選擇性質
比如所你是按每次裝入重量最小的作為貪心的選擇，那麼設重量從小到大（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）也是滿組貪心性質的最優解。矛盾。
❸ 活動安排問題的貪心選擇性質如何證明
設A是所給活動集合E=｛1，2，3，.....n｝的一個最優解，且A活動也是按結束時間非減序排列，A的第一個活動是k，若k=1，那麼A就是一個以貪心選擇開始的最優解，若k>1，則設
B=A-｛k｝∪｛1｝，由於f1<=fk,且A活動是相容的，所以B活動也是相容的，又由於A的活動個數與B的相同，故A是最優的，B也是最優的，也就是說，B是以貪心選擇活動1開始的最優活動安排，所以總存在以貪心選擇開始的最優活動安排方案。