Dotcpp > 试卷列表 > （连续邮资问题）某国发行了 n 种不同面值的邮票，并规

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规

"NOIP真题" 试卷中 NOIP第十三届全国青少年信息学奥林匹克联赛初赛试题[2007提高组] 中有题目如下：

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规定每封信最多允许贴 m 张邮票，在这些约束下，为了能贴出 {1 ， 2，3, …，maxvalue} 连续整数集合的所有邮资，并使 maxvalue 的值最大，应该如何设计各邮票的面值？例如，当 n=5 、m=4 时，面值设计为 {1 ， 3，11 ，15 ，32} ，可使 maxvalue 达到最大值 70 （或者说，用这些面值的 1 至4 张邮票可以表示不超过 70 的所有邮资，但无法表示邮资 71 。而用其他面值的 1 至4 张邮票如果可以表示不超过 k 的所有邮资，必有 k ≤70 ）。

下面是用递归回溯求解连续邮资问题的程序。数组 x[1:n] 表示 n 种不同的邮票面值，并约定各元素按下标是严格递增的。数组 bestx[1:n] 存放使 maxvalue 达到最大值的邮票面值（最优解），数组 y[maxl] 用于记录当前已选定的邮票面值 x[1:i] 能贴出的各种邮资所需的最少邮票张数。请将程序补充完整。

#include<stdio.h>
#defineNN20
#definemaxint30000
#definemaxl500/* 邮资的最大值 */
int n,m,bestx[NN],x[NN],y[maxl],maxvalue=0;
void result()
{ 
	输出结果：最大值： maxvalue 及 最优解： bestx[1:n] （略）
}
void backtrace(inti,intr)
{
	int j,k,z[maxl];
	for(j=0;j<= ① ;j++)
	if(y[j]<m)
	for(k=1;k<=m-y[j];k++)
	if(y[j]+k<=y[ ② ])
	y[ ③ ]=y[j]+k;
	while(y[r]<maxint)r++;
	if(i>n)
	{
		if(r-1>maxvalue)
		{
			maxvalue= ④ ; 
			for(j=1;j<=n;j++)
			bestx[j]=x[j];
		}
		return;
	}
	for(k=0;k<maxl;k++)
	z[k]=y[k];
	for(j= ⑤ ;j<=r;j++)
	{
		x[i]=j;
		⑥ ;
		for(k=0;k<maxl;k++)
		y[k]=z[k];
	}
}
void main()
{
	int j;
	printf("inputn,m:\n");
	scanf( "%d%d",&n,&m);
	for(j=1;j<maxl;j++)
	y[j]=maxint;
	y[0]=0;x[0]=0;x[1]=1;
	backtrace(2,1);
	result();
}

共 18 分　

所属试卷：NOIP第十三届全国青少年信息学奥林匹克联赛初赛试题[2007提高组]

其它题目

函数swap（a，n）可完成对a数组从第1个元素到第n

已知类Test的定义及程序段（静态成员、this指针相

下列枚举类型的定义中，包含枚举值3的是。

下列程序的运行结果是（）。

下列关于 CPU 中的数据通路和控制器的叙述中，错误的

软件（程序）调试的任务是（）。

给定程序中函数fun的功能是：根据整型形参m，计算如下

以下不能将键盘输入的字符串：This is a str

对于带有else子句的for循环和while循环，当循

已知 x = list（range （10）），则表达

关于C语言中 printf函数与 scanf函

以下程序运行结果是_________。

假设输入的所有数的绝对值都不超过1000，将第28行中

简述解决忘记root密码的办法。参考答案:1)用Red

在LINUX运行的7个级别中，X—WINDOWS图形系

在vi中退出不保存的命令是？

查看MySQL服务器上有哪些数据库的命令是

查看数据库中所有的数据表用以下哪一项( )

下面关于哈希(Hash，杂凑)查找的说法正确的是

软件生存周期一般可分为、可行性研究、、设计

预处理命令行都必须以_____号开始。

连接字符串的函数是_____，只写函数名即可。

在C语言中，格式输入操作是由库函数（只写函数名）___

函数proc的功能是：根据整型形参n，计算如下公式的值

输入：5输出：（）

目前计算机芯片（集成电路）制造的主要原料是（），它是

有 6 个城市，任何两个城市之间都有一条道路连接， 6

输入： Expo 2010 Shanghai Chin

输入： ABCDEFGuvwxyz输出： ______

已知 7 个结点的二叉树的先根遍历是 1245637

更多选择题

更多填空题

题量:	0 道
总分:	分

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷