回溯法解0-1背包问题实验报告

t b = cp; Р while (i<n&&bag[i].w<=cleft)Р {Р //以物品单位重量价值递减序装入Р cleft-=bag[i].w ;Р b+=bag[i].v;Р i++;Р } Р //装满背包Р if (i<n) b+=1.0*bag[i].v/bag[i].w * cleft;Р return b;Р}Рvoid Knapsack() //计算最优解和变量值Р{Р?int L(0); //用L累计价值,初始价值设置为0Р?for(int k=0;k<n;k++)Р?{Р x[bag[k].kk]=bag[k].flag; //x=0表示未放入背包,x=1表示放入背包РL+=bag[k].flag*bag[k].v; //价值累加Р?}Р?cout<<endl;Р?cout<<"当前最优价值为:"<<L<<endl;Р?cout<<"变量值 x = ";Р?for(int i=1;i<=n;i++)Р?{Р cout<<x[i-1];Р?}Р?delete []bag; bag=NULL;Р?delete []x; x=NULL;Р?cout<<endl; getch();Р}Рint main() Р{Р?cout<<endl;Р?cout<<"|**********回溯法解0-1背包问题**********|"<<endl;Р?Init();Р?Backtrack(0);Р?Knapsack();Р?return 0;Р}Р四、运行结果Р五、实验小结Р通过该实验,我充分了解了回溯法与分支界限法的区别。回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。