0-1背包问题 给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问选择装入背包的物品,使得装入背包中物品的总价值最大? 公式定义: 设所给0-1背包问题的子问题的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i,i+1,...,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下。 函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此,函数m(i,j)的全部跳跃点包含于函数m(i+1,j)的跳跃点集p[i+1]与函数m(i+1,j-wi)+vi的跳跃点集q[i+1]的并集中。,(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]。因此,容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]} 另一方面,设(a,b)和(c,d)是p[i+1]q[i+1]中的2个跳跃点,则当ca且d int Knapsack(int n,Type c,Type v[],Type w[],int **p,int x[]) { int *head = new int[n+2]; head[n+1]=0; p[0][0]=0;//p[][0]存储物品重量 p[0][1]=0;//p[][1]存储物品价值,物品n的跳跃点(0,0),相当于书上的Q // left 指向p[i+1]的第一个跳跃点,right指向最后一个 //拿书上的例子来说,若计算p[3]=0;则left指向p[4]的第一跳跃点(0 0)right指向(9,10) int left = 0,right = 0,next = 1;//next即下一个跳跃点要存放的位置 head[n]=1;//head[n]用来指向第n个物品第一个跳跃点的位置 for(int i=n; i>=1; i--) { int k = left;//k指向p[ ]中跳跃点,移动k来判断p[]与p[]+(w v)中的受控点 for(int j=left; j<=right; j++) { if(___1___) break;//剩余的空间不能再装入i,退出for循环; Type y = p[j][0] + w[i],m = p[j][1] + v[i];//计算p[ ]+(w v) //若p[k][0]较小则(p[k][0] p[k][1])一定不是受控点,将其作为p[i]的跳跃点存储 while(k<=right && ___2___) { p[next][0]=p[k][0]; p[next++][1]=p[k++][1]; } //如果 p[k][0]==y而m =y且m> =p[k][1],判断是不是当前i的最后一个跳跃点的受控点 //若不是则为i的跳跃点存储 if(m>__4__) { p[next][0]=y; p[next++][1]=m; } //若是,则对下一个元素进行判断。 while(k<=right && p[k][1]<=__5__) { k++; } } while(k<=right) { p[next][0]=p[k][0]; p[next++][1]=p[k++][1];//将i+1剩下的跳跃点作为做为i的跳跃点存储 } left = right + 1; right = next - 1; // 第i-1个物品第一个跳跃点的位置 head[0]指第0个物品第一个跳跃点的位置 head[i-1] = next; } Traceback(n,w,v,p,head,x); return p[next-1][1]; }