∥直到akm(0,akm(1,*)) w= st.GerTopo; st Pop();v=ww++;计算v=akm(1,*)+1 if( st IsEmpty(==0) ∥如果栈不空,改栈顶为(m-1,y) iw=st GetTopO: st Pop(): wvm wn=v: stPush( w):) I while(st. IsEmpro==0); 5-3【背包问题】设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为 v[1]lw(2]…,w[m。问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之 和正好为s。如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真):否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示:此 背包问题的递归定义如下:) 此时背包问题一定有解 False 总重量不能为负数 KNAP(s, n)= s>0且n<1物品件数不能为负数 KNAP(s,n-1)或>0且n≥1所选物品中不包括wn时 KNAP(s-wnl, n-1) 所选物品中包括n时 【解答】根据递归定义,可以写出递归的算法, enu boolean Knap( int s, int n)i if(s<0s>0&&n<1)return False; if( Knap(s-wIn] l)==True {cou≤<Wn]<‘,’; return True; return Knap(s, 1); 若设w={0,1,2,4,8,16,32},s=51,n=6。则递归执行过程如下 eturn True,完成 Kma(51-32,5) return True,打印3 nap(19-16,4 return True,打印16 nap(3-8, 3) return False Knap(3,3) return T return F Knap(3-4, 4) return False Knap(3, 2) return Tr s=-1<0 return False Knape3-2, 1)return True,打印2 Knap(1-1,0) I return True,打印1 return True 5-4【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1行,第2行,…。第8行上布放棋子。在每一行中有8个可选择位置,但在任一时刻,棋 盘的合法布局都必须满足3个限制条件,即任何两个棋子不得放在棋盘上的同一行、或者4 } //直到 akm( 0, akm( 1, * ) ) w = st.GetTop(); st.Pop( ); v = w.vn++; //计算 v = akm( 1, * )+1 if ( st.IsEmpty( ) == 0 ) //如果栈不空, 改栈顶为( m-1, v ) { w = st.GetTop(); st.Pop( ); w.vm--; w.vn = v; st.Push( w ); } } while ( st.IsEmpty( ) == 0 ); return v; } 5-3 【背包问题】设有一个背包可以放入的物品的重量为 s，现有 n 件物品，重量分别为 w[1], w[2], …, w[n]。问能否从这 n 件物品中选择若干件放入此背包中，使得放入的重量之 和正好为 s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此 背包问题的递归定义如下：）          − − −      = = ( [ ], 1) [ ] ( , 1) 0 1 [ ] False 0 1 False 0 True 0 ( , ) 所选物品中包括 时 或 且 所选物品中不包括 时 且 物品件数不能为负数 总重量不能为负数 此时背包问题一定有解 KNAP s w n n w n KNAP s n s n w n s n s s KNAP s n 【解答】根据递归定义，可以写出递归的算法。 enum boolean { False, True } boolean Knap( int s, int n ) { if ( s == 0 ) return True; if ( s < 0 || s > 0 && n < 1 ) return False; if ( Knap ( s – W[n], n-1 ) == True ) { cout << W[n] << ‘ , ’; return True; } return Knap( s, n-1 ); } 若设 w = { 0, 1, 2, 4, 8, 16, 32 }，s = 51, n = 6。则递归执行过程如下 递 归 Knap(51, 6) return True, 完成 Knap(51-32, 5) return True, 打印 32 Knap(19-16, 4) return True, 打印 16 Knap(3-8, 3) return False Knap(3, 3) return True, 无动作 s = -5 < 0 return False Knap(3-4, 4) return False Knap(3, 2) return True, 无动作 s = -1 < 0 return False Knap(3-2, 1) return True, 打印 2 Knap(1-1, 0) return True, 打印 1 s = 0 return True 5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1 行，第 2 行，…。第 8 行上布放棋子。在每一行中有 8 个可选择位置，但在任一时刻，棋 盘的合法布局都必须满足 3 个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者