7、
8、abs(k-i)==abs(x[k]-x[i]))returnfalse;returntrue;}voidqueue(intn){inti,k;for(i=1;i<=n;i++)x[i]=O;k=1;while(k>=1){刈k]=刈k]+1;//在下一列放置第k个皇后while(x[k]<=n&&!place(k))x[k]=x[k]+1;//搜索下一列if(x[k]<=n&&k==n)//得到一个输出{for(i=1;i<二n;i++)printf("%d
9、”,x[i]);//return;//若return则只求出其中一种解,若不return则可以继续回溯,求出全部的可能的解}elseif(x[k]<=n&&kvn)k=k+1;//放置下一个皇后else{x[k]=O;//M置x[k],回溯k=k-1;}}}voidmain(){intn;printf("输入皇后个数n:");scanf(”％d”,&n);queue(n);1.(0邛背包问题)有N件物品d1,……dN,每件物品重量为W1,・WN(Wi>0),每件物品价值为W,……VN(Vi>0)。从这N件物品屮选
10、部分物品製入背包，使背包内物品的总重量不超过背包的容量TOTAL,并使背包屮物品的总价值最高。(采用递归回溯求解)2.(多项式乘法)编写计算两个多项式相乘P(x)Q(x)=R(x)的函数：voidmuity(floata[],intm,floatb[],intn,floatc[],int*k);其小数组a[],b[],c[]分别存放三个多项式的系数,m,n,k分别是多项式P(x)、Q(x)、R(x)的次数，通过形参与实参的结合返回c[],k的值。3.(全部排列)给定n个不同的数字(n<10),利用递归方式编程求这n个
11、数字的全部可能的排列。要求包括:算法简介，源程序，对主要变量和重要语句的注释，运行结呆的说明1背包问题是一个非常有名的问题•可以这样叙述如下•假设有n件物品，记为d1,d2,d3,dn.对于每一种物品di(1==v3/w3>=v4/w4>=v5/w5,这样算法再考虑将物品放入背包时，首先考虑的是取单价尽可能高的物品，以使背包的价值尽量大.在以后的程序8.1中,也遵循这样的惯例.程序8.1背包问题的类knap的定义及背包问题的解法typedefstructwvm{floatweight;//当前的重量floatval;
12、//当前的价值intm;//当前考察的物品件数.}WVM;//解答空间树屮的结点类型.includeincludeusingnamespacestd;templateclassknap{friendvoidknapsack(knap&);public:knap(constTypewtotal,constintnum,Typep&value,Typeww1[],Typepv1[])；〜knap(){delete[]w;delete[]v;}private:Typepf(Typewremnant,inti);//从i+1
13、物品开始计算，背包的剩余重量remnant//可以达到的价值的最大上界.TypewTOT;//背包的重量限制，如上例为TOT为37.intn;//给定的物品件数，如上例为n为5.Typew*w;//n件物品的重量数组.Typep*v;//n件物品的价值数组.TypepY;//得到的背包最优价值，初值为0.}；templateknap::knap
