數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)___背包問題的求解

1、2009屆電子信息科學(xué)與技子信息科學(xué)與技術(shù)專業(yè)術(shù)專業(yè)數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)1背包問題的求解背包問題的求解摘要組合優(yōu)化問題的求解方法研究已經(jīng)成為了當(dāng)前眾多科學(xué)關(guān)注的焦點(diǎn)，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價(jià)值，同時(shí)也在于它們能在現(xiàn)實(shí)生活中廣泛的應(yīng)用。背包問題是一個典型的組合優(yōu)化問題，本課程設(shè)計(jì)用遞歸算法求解背包問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。關(guān)鍵詞背包問題；遞歸算法；1問題描述1.1問題描述背包問題

2、：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價(jià)值之和最大。1.2基本思想（1）分別輸入n件物品的重量和價(jià)值。（2）采用遞歸尋找物品的方案。（3）輸出最佳的裝填方案，包括選中的是哪幾種物品，總價(jià)值為多少。2問題分析背包問題的求解是一個很經(jīng)典的案例。對于它的分析與研究已經(jīng)到達(dá)了一定的深度，解決這個問題有很多很多的辦法。其中遞歸方法是比較簡化程序，也比較難理解的一個

3、。設(shè)n件物品的重量分別為w0w1…wn1物品的價(jià)值分別為v0v1…vn1。采用遞歸尋找物品的選擇方案。設(shè)前面已經(jīng)有了多種選擇方案，并保留了其中最大的選擇方案于數(shù)組option[]設(shè)方案的的總價(jià)值存于變量maxv當(dāng)前正在考察新方案其物品選擇情況保存于數(shù)組cop[]，嘉定當(dāng)前方案已經(jīng)考慮了前i1件物品，現(xiàn)在正在考慮第i件物品；當(dāng)前方案已經(jīng)包含的物品的質(zhì)量之和為tw至此，若其余物品都選擇可能的話，本方案能達(dá)到的總價(jià)值的期望值設(shè)為tv，算法引入

4、tv是當(dāng)一旦當(dāng)前方案的總價(jià)值的期望值也小于前面方案的總價(jià)值maxv時(shí)，急需考察當(dāng)前方案變成無意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會不會再被考察。這同時(shí)保證函數(shù)后找到的方案一定會比前面的方案更好。2009屆電子信息科學(xué)與技子信息科學(xué)與技術(shù)專業(yè)術(shù)專業(yè)數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)3圖41程序流程圖4.2算法設(shè)計(jì)根據(jù)問題分析中的思想寫出遞歸算法如下：find（物品當(dāng)前選擇已達(dá)到的重量和tw本