1、.購物單問題的回溯搜索算法分析與研究李綿梁（陜西師范大學(xué)，西安，710062）摘要：購物單問題是一個典型的0-1背包問題。而0-1背包問題是算法分析設(shè)計中的經(jīng)典問題，本文通過回溯搜索算法來解決購物單問題，并對該算法時間復(fù)雜度進(jìn)行理論上和實際上的分析比較。關(guān)鍵詞：購物單問題 0-1背包 回溯搜索一、 問題描述：小明被評為省級三好學(xué)生，媽媽決定獎勵他n元。小明就開始做預(yù)算，但是他想買的東西太多了，肯定會超過媽媽限定的n元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)15表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過n元的前提下，使每件物品的價格和重要度

2、的乘積的總和最大。設(shè)第j件物品的價格為vj，重要度為wj，共選中了k件物品，編號依次為j1，j2,jk,則所求總和為:vj1*wj1+vj2*wj2+vjk*wjk請你幫小明設(shè)計一個滿足要求的購物單。二、 算法分析與數(shù)學(xué)建模：假設(shè)：所買的東西都是獨立的，即沒有相互間的依賴關(guān)系。則對于每一件物品而言，只有買或不買兩種情況，而物體本身也不可分，并且所買物體總數(shù)受總錢數(shù)所限，目標(biāo)為所求重要性1盡可能大。因此，該問題是一個典型的0/1 背包問題！推廣到一般，對于n件物品，假設(shè)對其進(jìn)行依次編號1，2，3，n，不妨將第i件物品購買狀況記為fi(fi=0,1),即將購買第i件物品記為fi=1，不購買記為fi

3、=0，則通過分析不難得出，該問題的數(shù)學(xué)模型為：精品.1. 重要性：本文定義為物體重要度與價格的乘積。從算法復(fù)雜性理論來看，該問題是一個np問題。而目前，對該類問題的解決方法也是非常多的，主要包括分支限界法、群舉法、圖論法、貪心算法、蟻群算法等。本文作者用回溯搜索算法對問題進(jìn)行求解與分析討論。在題目約束條件（總價格不超過n元）的前提下，對問題解空間構(gòu)成的樹進(jìn)行回溯搜索。在遍歷過程中，只有當(dāng)前物品需要購買時（值為1），才需要進(jìn)行購買后價格是否超過總n元的判斷，若不超過，才需要進(jìn)行更深的搜索；若判斷購買后總價格大于n元，則無需進(jìn)行更深的搜索。三、 算法實現(xiàn)在算法實現(xiàn)過程中需要增加輔助變量如下：記錄物

4、品重要性、價格分別為數(shù)組w、v；記錄總錢數(shù)為tm。在每次搜索過程中，記錄當(dāng)前搜索結(jié)果的當(dāng)前最大重要性、當(dāng)前花費錢數(shù)分別為cmax、total，當(dāng)前最大重要性下對物品的取舍情況t；記錄每次搜索對物品的取舍狀態(tài)數(shù)組sign；設(shè)計回溯搜索的核心算法如下：void www(int i) / 從第i層開始;int j;float sum=0; / 當(dāng)前分支重要性總和if (i=n+1) / 到達(dá)葉結(jié)點for (j=0;jcmax) cmax=sum; / 更改重要性for (j=0;jn;j+)tj=signj;精品.return; signi-1=0; / 未到葉節(jié)點，不買第i件物品時;www(i+1

5、);if (total+vi-1=tm) / 可買第i件物品的情況;signi-1=1;total+=vi-1;www(i+1);signi-1=0;total-=vi-1;/ 回溯之前清理現(xiàn)場;四、 算法復(fù)雜度分析1. 理論分析在搜索過程中，對于不同的n，算法進(jìn)行搜索的情況都不同。但該算法需要搜索的問題解空間共有2n個分支，因此，算法時間復(fù)雜度為o(2n)。2. 實際分析對實驗進(jìn)行統(tǒng)計，其統(tǒng)計結(jié)果如表一所示：表一：實際實驗時間復(fù)雜度數(shù)量n2345678時間t11.858771.883872.162172.445373.158225.594057.94152時間t21.690441.81702

6、2.108722.373603.127125.569218.35889時間t31.642331.885122.110972.227273.154795.618487.82389時間t41.648582.001362.035372.328613.140165.615887.76655時間t51.680781.928252.041902.339033.0375.762247.79614平均時間1.704181.9031242.0918262.3426863.1234585.6319727.9373983. 理論與實際的比較對理論情況與實際實驗情況的結(jié)果進(jìn)行對比，其時間復(fù)雜度圖一所示。精品.圖一：理論與實際時間復(fù)雜度對比圖由以上圖示可以看出，實驗理論時間復(fù)雜度與實際復(fù)雜度結(jié)果近似相似，因此可以說明該算法是正確的。五、 結(jié)論0/1背包問題有許多算法，本文作者只是用回溯搜索算法對問題進(jìn)行解決，并根據(jù)實際實驗復(fù)雜度與理論實驗復(fù)雜度進(jìn)行詳細(xì)比較，來判斷討論出實際算法的正確性。本文只是用一種算法對問題進(jìn)行解決是很局限的，也未能夠通過對不同算法時間復(fù)雜度的比較而得出更