算法设计与分析 课件 第六章 回溯法6.3.1 饲料投喂问题 -算法改进

计算机算法设计与分析第6章回溯法6.3.1饲料投喂问题---算法改进给定任意状态[x1，x2，...，xk]，怎么来判断其子结点是否可能得出最优解？ABCx1，x2，...，xk，1x1，x2，...，xk，0x1x1，x2，...，xk进入左分支结点B，xk+1=1,设cw=,若cw+wk+1>C用约束函数对A的左分支进行剪枝处理算法改进给定任意状态[x1，x2，...，xk]，怎么来判断其子结点是否可能得出最优解？ABCx1，x2，...，xk，1x1，x2，...，xk，0x1x1，x2，...，xk进入结点A的右分支结点C，xk+1=0，cw≤C,总是可行右分支上的投喂可能的最大产奶量为cv+若cv+<=bestv,不可能是最优解，可剪枝饲料余量为C-cw，后续奶牛的产奶量为算法改进现在的问题是

如何计算？这部分是还没有考虑投喂的奶牛最大产奶量，属于未知的，所以仅对其上限进行粗略的评估。算法改进常用的评估方法为=在不考虑现有饲料余量的情况下，后面的奶牛全部产奶的总和，若cv+>bestv，则进入结点A的右分支，否则剪枝处理。c语言实现剪枝函数，评估后面奶牛产奶量的最大极值intbound(inti,intcw,intcv){intbv=cv;for(intj=i;j<n;j++)bv+=v[j];returnbv;}//饲料投喂问题（0-1背包问题）的递归回溯函数voidbacktrack(inti,intcw,intcv){if(i==n){if(cv>bestv&&cw<=c){ bestv=cv; for(intk=0;k<n;k++)bestx[k]=x[k];}return;}if(cw+w[i]<=c){cv+=v[i];cw+=w[i];x[i]=1;backtrack(i+1,cw,cv);

cv-=v[i];cw-=w[i];//若剪枝需要回溯}if(bound(i+1,cw,cv)>bestv){ x[i]=0;backtrack(i+1,cw,cv);}}进入左分支的剪枝约束条件进入右分支的剪枝限界条件与前一节一样进一步优化为了对进入右分支的限界函数进一步优化，考虑现有饲料余量下精准评估

的值。可以在问题处理前，我们按单位重量投喂饲料后牛奶产出量的降序，重新将奶牛进行编号。按照这种顺序，只要饲料还够，就进行投喂，并计算其产奶量；当考虑到某头奶牛时，剩下的饲料不足投喂它，则用剩下的饲料对它进行部分投喂，并计算部分投喂可能的产奶量，并将产奶量累计计算结果作为

的评估值，相较前面不考虑剩余饲料量的评估会更为精准。进一步优化后的评估限界函数//剪枝限界函数的c语言代码doublebound(inti,intcw,intcv){doublebv=cv;inttw=cw;for(intj=i;j<n;j++){if(tw+w[j]<=c){bv+=v[j];tw+=w[j];}else{doublerc=c-tw;bv+=(rc*v[j])/w[j];break;}}returnbv;}已产生的价值（产奶量）已消耗的背包容量（饲料量）已消耗的背包容量+当前投喂量<总量当前不足投喂，则部分投喂进行计