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

计算机算法设计与分析第6章回溯法6.3.1饲料投喂问题饲料投喂问题：某农场有n头奶牛，假设每头奶牛仅有投喂或不投喂饲料两种选择，奶牛i需要投喂wi千克饲料才能产出vi千克牛奶。农场现有饲料总量为C千克，问如何投喂才能使得奶牛产奶量最大化？6.3.1饲料投喂问题农场奶牛饲料投喂问题是一个典型的0-1背包问题，假设农场有n=4头奶牛，农场饲料总量C为10千克，每头奶牛需要的饲料量和能够产出的牛奶量如下，w_i投喂饲料重量，v_i投喂后的产量。牛奶编号w_iv_i12523835144521问题的解向量空间奶牛投喂的解向量空间可以表示为一个四元组X=(x1,x2,x3,x4)，xi的值表示第i头奶牛投喂情况。由于每头奶牛仅有投喂或不投喂饲料两种选择，所以xi(i=1,2,3,4,表示奶牛编号)只能取值为0或1，xi=0表示不投喂，xi=1表示进行投喂。解空间树用回溯法求解，需要生成一棵二叉树（子集树）来表示问题的解空间。x4=1,2+3+5+510不可行，回溯?ABx4=0x4=1,5+5≤10x3=1,510x2=0,C=10x1=0,C=10初始状态，饲料总量C=10x1=1,210x2=1,2+310x3=1,2+3+5≤10编号w_iv_i12523835144521数学建模C语言实现voidbacktrack(inti,intcw,intcv){ if(i==n){ if(cvbestvcw=C){ bestv=cv; for(intk=0;kn;k++)bestx[k]=x[k]; } return; } x[i]=1; backtrack(i+1,cw+w[i],cv+v[i]); x[i]=0; backtrack(i+1,cw,cv);}bestv记录下前最优值x[i]=1,递归到下一层x[i]=0,递归到下一层bestx记录当前最优解效率分析深度优先有哪些信誉好的足球投注网站回溯法求解饲料投喂问题（0-1背包问题）的时间复杂度分析，由问题解空间树可知，n头奶牛投喂过程产生的解空间树，其结点总数为：1+2+22+...+2n=2n+1-1≤2*2n=O(2n)。效率是比较低的，时间复杂度O(2n)是一个指数数量级。若要提高执行效率，需要设计剪枝函数对解向量空间树进行剪枝，剪除那些不可能得出可行解和最优解的分支，以减少不必要的有哪些信誉好的足球投注网站。**