1、算法分析實驗報告貪心法解決背包問題學生姓名： 專 業： 班 級： 學 號: 指導教師： 2017年 6月12日目錄一、實驗題目2二、實驗目的2三、實驗要求2四、實現過程31、實驗設計：32、調試分析53、運行結果：64、實驗總結：6五、參考文獻6一、實驗題目貪心法解決背包問題二、實驗目的1）以背包問題為例，掌握貪心法的基本設計策略。2）熟練掌握各種貪心策略情況下的背包問題的算法并實現；其中：量度標準分別取：效益增量v、物品重量w、v/ w比值；3) 分析實驗結果來驗證理解貪心法中目標函數設計的重要性。三、實驗要求1.問題描述：給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量

2、為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，但不可以重復裝入。2.算法：貪心法的基本思路：從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某算法中的某一步不能再繼續前進時，算法停止。該算法存在問題：1）不能保證求得的最后解是最佳的；2）不能用來求最大或最小解問題；3） 只能求滿足某些約束條件的可行解的范圍。四、實現過程1、實驗設計：1.用貪心法求解背包問題的關鍵是如何選定貪心策略，使得按照一定的順序選擇每個物品，并盡可能的裝入背包，直至背包

3、裝滿。至少有三種看似合理的貪心策略：1）按物品價值v降序裝包，因為這可以盡可能快的增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗太快，使得裝入背包得物品個數減少，從而不能保證目標函數達到最大。2）按物品重量w升序裝包，因為這可以裝入盡可能多的物品，從而增加背包總價值。但是，雖然每一步選擇使背包得容量消耗得慢了，但背包價值卻沒能保證迅速增長，從而不能保證目標函數達到最大。3）按物品價值與重量比值v/w的降序裝包。2.設背包容量為C，共有n個物品，物品重量存放在數組wn中，價值存放在數組vn中，問題的解存放在數組xn中，貪心法求解背包問題的算法如下。輸入：背包

4、容量為C，物品重量wn，物品價值vn輸出：數組xn1） 改變數組w和v的排列順序，使其按單位重量價值vi/wi降序排列；2） 將數組xn初始化為0；3） i=0；4） 循環直到（wi>C）a. 將第i個物品放入背包：xi=1;b. C=C-wi;c. i+;5） xi=C/wi。3.流程圖物品iwi>Cxi=1C=C-wii+i<n退出循環inxi=C/wi程序結束4.算法實現int KnapSack(int n,int w,int v,int C)double x10=0;int maxValue=0;for (int i = 0; wi < C; i+)xi=1;maxValue+=vi;C=C-wi;xi=(double)C/wi;maxValue+=xi*vi;return maxValue;2、調試分析在算法KnapSack中，時間主要消耗在將各種物品按照單位重量的價值從大到小排序。因此，其時間復雜度為O(nn)。3、運行結果：4、實驗總結： 通過本次實驗我們了解了背包問題貪心法的基本思想和策略，我們發現用該方法解決此問題的核心在于對量度標準的選擇，通過具體數據的解答，我們最終確定了以單位效益，即物品的權值和重量的比值為量度最終能得到背包問題貪心法的最優解，同時也使我們對貪心法這一策略有了更為直觀的認識。五、參考文