貪心法解決背包問題

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