1、購物清單問題的回溯搜尋演算法分析研究雙面量(陜西師范大學(xué)，西安市，710062)摘要：購物清單問題是典型的0-1背包問題。背包問題0-1是算法分析設(shè)計的經(jīng)典問題。在牙齒文件中，通過算法反向搜索解決購物清單問題，進(jìn)行算法時間復(fù)雜度理論和實際分析比較。關(guān)鍵字：購物清單問題0-1背包回溯搜尋一、問題說明：小明被評為省級三大學(xué)生，媽媽決定獎勵他N元。小明開始做預(yù)算，但是他想買的東西太多，會超過媽媽限定的N元。所以他把每件東西的重要性定為5級。整數(shù)15，5等是最重要的。他還在網(wǎng)上找到了各項目的價錢(都是整數(shù))。他希望將每個項目的價錢及重要性的乘積加在一起，除非超過N元。我j料號的價錢vj，重要性wj，料

2、號k總計，編號J1，J2，JK，總計：vJ1* wJ1v；請幫助小明設(shè)計符合要求的購物清單。二、算法分析和數(shù)學(xué)建模：假設(shè)：買的東西都是獨立的。也就是說，沒有相互依存。對于每件物品，只能購買或不購買兩種茄子情況，物體本身也不能分離，購買的物體總數(shù)受總數(shù)的限制，目標(biāo)是盡量求重要性1。所以牙齒問題是典型的0/1背包問題！一般而言，N個料號為1，2，3，您可以編號n，將I料號的采購情況記錄為fi(fi=0，1)，很快將I料號的采購記錄為fi1.重要性：牙齒文檔由對象重要性和價錢乘積定義。從算法復(fù)雜性理論來看，牙齒問題是NP問題?，F(xiàn)在對牙齒等問題的解決方法也很多。主要有分支限制法、軍旅法、圖論、貪心算法

3、、螞蟻種群算法等。牙齒文章的作者利用回溯搜尋演算法解決問題，分析和討論。以標(biāo)題約束(總價錢n元以下)為前提，反向搜索問題解決空間構(gòu)成的樹。在巡回過程中，需要購買當(dāng)前項目時(值為1)，要判斷購買后價錢總額是否超過N元，如果不超過，則需要進(jìn)行更深的搜索。購買后，如果認(rèn)為價錢總數(shù)大于N韓元，就不需要進(jìn)行更深的搜索。三、算法的實施在算法實施過程中，必須添加輔助變量，如下所示：記錄料號重要性，價錢陣列w，V；把貨幣總數(shù)記為TM。在每個搜索過程中，記錄當(dāng)前搜索結(jié)果的當(dāng)前最大重要性，當(dāng)前支出分別為Cmax、total、當(dāng)前最大重要性的項目選擇t；每次搜索時，物品的餐飲狀態(tài)陣列sign；設(shè)計回溯搜尋的核心算法：從Void www(int i) /層I開始：int j；float sum=0；/當(dāng)前季度重要性合計If (i=n