貪心法解決背包問題

算法分析實驗報告貪心法解決背包問題學(xué)生姓名:專業(yè):班級:學(xué)號:指導(dǎo)教師:2017年6月12日目錄TOC\o"1-5"\h\z\o"CurrentDocument"一、實驗題目 2\o"CurrentDocument"二、實驗?zāi)康?2\o"CurrentDocument"三、實驗要求 2\o"CurrentDocument"四、實現(xiàn)過程 3\o"CurrentDocument"1、實驗設(shè)計： 3\o"CurrentDocument"2、調(diào)試分析 53、運行結(jié)果： 6\o"CurrentDocument"4、實驗總結(jié)： 6\o"CurrentDocument"五、參考文獻 6一、實驗題目貪心法解決背包問題二、實驗?zāi)康?）以背包問題為例，掌握貪心法的基本設(shè)計策略。2）熟練掌握各種貪心策略情況下的背包問題的算法并實現(xiàn)；其中:量度標準分別?。盒б嬖隽縱、物品重量w、v/w比值；3）分析實驗結(jié)果來驗證理解貪心法中目標函數(shù)設(shè)計的重要性。三、實驗要求.［問題描述］:給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，但不可以重復(fù)裝入。.［算法］：貪心法的基本思路：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當(dāng)達到某算法中的某一步不能再繼續(xù)前進時，算法停止。該算法存在問題：1）不能保證求得的最后解是最佳的；2）不能用來求最大或最小解問題；3）只能求滿足某些約束條件的可行解的范圍。四、實現(xiàn)過程1、實驗設(shè)計：.用貪心法求解背包問題的關(guān)鍵是如何選定貪心策略，使得按照一定的順序選擇每個物品，并盡可能的裝入背包，直至背包裝滿。至少有三種看似合理的貪心策略：1）按物品價值v降序裝包，因為這可以盡可能快的增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗太快，使得裝入背包得物品個數(shù)減少，從而不能保證目標函數(shù)達到最大。2）按物品重量w升序裝包，因為這可以裝入盡可能多的物品，從而增加背包總價值。但是，雖然每一步選擇使背包得容量消耗得慢了，但背包價值卻沒能保證迅速增長，從而不能保證目標函數(shù)達到最大。3）按物品價值與重量比值v/w的降序裝包。.設(shè)背包容量為C，共有n個物品，物品重量存放在數(shù)組w[n]中，價值存放在數(shù)組v[n]中，問題的解存放在數(shù)組x[n]中，貪心法求解背包問題的算法如下。輸入：背包容量為C，物品重量w[n]，物品價值v[n]輸出：數(shù)組x[n]改變數(shù)組w和v的排列順序，使其按單位重量價值v[i]/w[i]降序排列；將數(shù)組x[n]初始化為0；i=0；循環(huán)直到(w[i]>C)a.將第i個物品放入背包：x[i]=1;C=C-w[i];i++;x[i]=C/w[i]o.流程圖4.算法實現(xiàn)intKnapSack(intn,intw[],intv[],intC)(doublex[10]={0};intmaxValue=0;for(inti=0;w[i]<C;i++){x[i]=1;maxValue+=v[i];C=C-w[i];}x[i]=(double)C/w[i];maxValue+=x[i]*v[i];returnmaxValue;}2、調(diào)試分析在算法KnapSack中，時間主要消耗在將各種物品按照單位重量的價值從大到小排序。因此，其時間復(fù)雜度為O(nlogn)。3、運行結(jié)果:的的的的A人人入的的的的A人人入放放放-J'品品品(4、實驗總結(jié)：通過本次實驗我們了解了背包問題貪心法的基本思想和策略，我們發(fā)現(xiàn)用該方法解決此問題的核心在于對量度標準的選擇，通過具體數(shù)據(jù)的解答，我們最終確定了以單位效益，即物品的權(quán)值和重量的比值為量度最終能得到背包問題貪心法的最優(yōu)解，同時也使我們對貪心法這一策