實驗四回溯算法和分支限界法

1、實驗四 回溯算法和分支限界法0-1背包問題一、實驗目的:1、掌握0-1背包問題的回溯算法；2、進一步掌握回溯算法。二、實驗內(nèi)容給定n和物品和一人背包，物品i的重量是wi，其價值為vi，問如何選擇裝入背包的物品，使得裝入背包的物品的總價值最大？三、實驗步驟1、代碼/ HS_ALG.cpp : Defines the entry point for the console application./#include #include using namespace std;/ 物體結(jié)構(gòu)體typedef structfloat w; /物品重量float p; /物品價值float v; /背包體積

2、int id; /物品個數(shù)OBJECT;bool cmp(OBJECT a, OBJECT b /比較兩物品體積return a.v>b.v;float knapsack_back(OBJECT ob, float M, int n, bool x /回溯法int i,k;float w_cur, p_total, p_cur, w_est, p_est;bool *y = new booln+1;/ 計算物體的價值重量比for(i=0; i<=n; i+obi.v = obi.p/obi.w;yi = false;/ 按照物體的價值重量比降序排列sort(ob, ob+n, cm

3、p;/ 初始化當前背包中的價值、重量w_cur = p_cur = p_total = 0;/ 已搜索的可能解的總價值初始化k = 0;while(k>=0w_est = w_cur; p_est = p_cur;/ 沿當前分支可能取得的最大價值for( i=k; i w_est += obi.w;if(w_est p_est += obi.p;elsep_est += (M-w_est+obi.w/obi.w*obi.p;break;/ 估計值大于上界if(p_est>p_totalfor(i=k; i if(w_cur+obi.w<=M/ 可裝入第i個物體w_cur =

4、w_cur + obi.w;p_cur = p_cur + obi.p;yi = true;else/ 不能裝入第i個物體yi = false;break;if(i>=n/ n個物體已經(jīng)全部裝入if(p_cur>p_total/ 更新當前上限p_total = p_cur;k = n;/ 保存可能的解for(i=0; i xi = yi;else/ 繼續(xù)裝入物體k = i+1;else/ 估計值小于上界時while(i>=0&&(!yii-; / 沿著右分支結(jié)點方向回溯直到左分支結(jié)點if(i<0break; / 到達根結(jié)點 算法結(jié)束else / 修改當前

5、值w_cur -= obi.w;p_cur -= obi.p;yi = false;k = i+1; / 搜索右分支子樹/delete y;return p_total;int main(int n;float m;cout<<"請輸入背包載重："cin>>m;cout<<"請輸入物品個數(shù)："cin>>n;OBJECT* ob = new OBJECTn;cout<<"請輸入物品的重量、價格："< for(int i=0; i cin>>obi.w>>obi.p;obi.id = i+1;bool* x = new booln;float v = knapsack_back(ob, m, n, x;cout<<"最優(yōu)方案："< for(int i=0; i if(xicout<<