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

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

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

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

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