实验四回溯算法和分支限界法

1、实验四 回溯算法和分支限界法0-1背包问题一、实验目的:1、掌握0-1背包问题的回溯算法；2、进一步掌握回溯算法。二、实验内容给定n和物品和一人背包，物品i的重量是wi，其价值为vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？三、实验步骤1、代码/ HS_ALG.cpp : Defines the entry point for the console application./#include #include using namespace std;/ 物体结构体typedef structfloat w; /物品重量float p; /物品价值float v; /背包体积

2、int id; /物品个数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个物体已经全部装入if(p_cur>p_total/ 更新当前上限p_total = p_cur;k = n;/ 保存可能的解for(i=0; i xi = yi;else/ 继续装入物体k = i+1;else/ 估计值小于上界时while(i>=0&&(!yii-; / 沿着右分支结点方向回溯直到左分支结点if(i<0break; / 到达根结点 算法结束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<<"请输入物品个数："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<<"最优方案："< for(int i=0; i if(xicout<<