文档介绍：备战ACM资料****题1. 0-1背包问题在0/1背包问题中,需对容量为c的背包进行装载。从n个物品中选取装入背包的物品,每件物品i的重量为wi,价值为pi。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。程序如下:#include<>voidreaddata();voidsearch(int);voidcheckmax();voidprintresult();intc=35,n=10;//c:背包容量;n:物品数intw[10],v[10];//w[i]、v[i]:第i件物品的重量和价值inta[10],max;//a数组存放当前解各物品选取情况;max:记录最大价值//a[i]=0表示不选第i件物品,a[i]=1表示选第i件物品intmain(){ readdata();//读入数据 search(0);//递归搜索 printresult();}voidsearch(intm){ if(m>=n) checkmax();//检查当前解是否是可行解,若是则把它的价值与max比较 else { a[m]=0;//不选第m件物品 search(m+1);//递归搜索下一件物品 a[m]=1;//不选第m件物品 search(m+1);//递归搜索下一件物品 }}voidcheckmax(){ inti,weight=0,value=0; for(i=0;i<n;i++) { if(a[i]==1)//如果选取了该物品{ weight=weight+w[i];//累加重量 value=value+v[i];//累加价值} } if(weight<=c)//若为可行解 if(value>max)//且价值大于max max=value;//替换max}voidreaddata(){ inti; for(i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);//读入第i件物品重量和价值}voidprintresult(){ printf("%d",max);}2. 装载问题有两艘船,载重量分别是c1、c2,n个集装箱,重量是wi(i=1…n),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。提示:求出不超过c1的最大值max,若总重量-max<c2则能装入到两艘船。3. 堡垒问题(ZOJ1002)如图城堡是一个4×4的方格,为了保卫城堡,现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙,其余格子都是空格,堡垒只能建在空格里,每个堡垒都可以向上下左右四个方向射击,如果两个堡垒在同一行或同一列,且中间没有墙相隔,则两个堡垒都会把对方打掉。问对于给定的一种状态,最多能够修建几个堡垒。程序主要部分如下:intmain(){ readdata();//读入数据 search(0);//递归搜索 printresult();}voidsearch(intm){ introw,col; row=m/n;//求第m个格子的行号 col=m%n;//求第m个格子的列号 if(m>=n*n) checkmax();//检查当前解是否是可行解,若是则把它的价值与max比较 else { search(m+1);//该位置不放堡垒递归搜索下一个位置 if(canplace(m))//判断第m个格子是否能放堡垒{ place(m);//在第m个格子上放置一个堡垒 search(m+1);//递归搜索下一个位置 takeout(m);//去掉第m个格子上放置的堡垒} }}5. 8皇后问题在一个8×8的棋盘里放置8个皇后,要求这8个皇后两两之间互相都不“冲突”。#include<>#include<>voidsearch(int);voidprintresult();//打印结果intcanplace(int,int);//判断该位置能否放置皇后voidplace(int,int);//在该位置能否放置皇后voidtakeout(int,int);//把该位置放置皇后去掉inta[8];//a[i]存放第i个皇后的位置intmain(){ search(0);//递归搜索}voidsearch(intm){ inti; if(m>=8)//当已经找出一组解时 printresult();//输出当前结果 else { for(i=0;i<8;i++)//对当前行0到7列的每一个位置{ if(canplace(m,i))//判断第m个格子是否能放堡垒{ place(m,i);//在(m,i)格子上放置一个皇后 search(m+1);//递归搜索下一行 takeout(m,i);//把(m,i)格子上的皇后去掉} } }}in