ACM程序设计竞赛例题[1].doc

《ACM程序设计竞赛例题[1].doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、备战ACM资料习题1．0-1背包问题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。程序如下：#includevoidreaddata();voidsearch(int);voidcheckmax();voidprintresult();intc=35,n=10;//c：背包容量；n：物品数intw[10],v[10];//w[i]、v[i]：第

2、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件

3、物品search(m+1);//递归搜索下一件物品}}voidcheckmax(){inti,weight=0,value=0;for(i=0;imax)//且价值大于maxmax=value;//替换max}voidreaddata(){inti;for(i=0;i

4、&w[i],&v[i]);//读入第i件物品重量和价值}voidprintresult(){printf("%d",max);}2．装载问题有两艘船，载重量分别是c1、c2，n个集装箱，重量是wi(i=1…n)，且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。提示：求出不超过c1的最大值max，若总重量－max

5、格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。程序主要部分如下：intmain(){readdata();//读入数据search(0);//递归搜索printresult();}voidsearch(intm){introw,col;row=m/n;//求第m个格子的行号col=m%n;//求第m个格子的列号if(m>=n*n)checkmax();//检查当前解是否是可行解，若是则把它的价值与max比较

6、else{search(m+1);//该位置不放堡垒递归搜索下一个位置if(canplace(m))//判断第m个格子是否能放堡垒{place(m);//在第m个格子上放置一个堡垒search(m+1);//递归搜索下一个位置takeout(m);//去掉第m个格子上放置的堡垒}}}5．8皇后问题在一个８×８的棋盘里放置８个皇后，要求这8个皇后两两之间互相都不“冲突”。#include#includevoidsearch(int);voidprintresult();//打印结果intc

7、anplace(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))

8、//判断第m个格子是否能放堡垒{place(m,i);//在(m,i)格子上放置一个皇后search(m+1);//递归搜索下一行takeout(m,i);//把(m,i)格子上的皇后去掉}}}}intcanplace(introw,intcol){inti;for(i=0;i