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提高组]

其它题目

有如下类定义，编译时发现有一处语法错误，对这个错误最准

当一个包含Applet的Web页面被其他页面覆盖时，被

给定程序MODI1.C中函数fun功能是：将长整型数中

下面描述中错误的是（）。

C语言编译程序的功能是（）。

若在程序中变量均已定义成int类型，且已赋大于1的值，

有以下程序：执行时若输入以下字符串：Peach flo

若有定义语句：则表达式'A'+a+b值的类型是。

已知 x={1:2，2:3}，那么表达式 x.get

只能通过切片访问列表中的元素，不能使用片修改列表中的元

表达式3|5的值为_______。

下面程序运行成果是（）。

以下fun函数的功能是：找出具有N个元素的一维数组中的

属于同一进程的两个线程thread1和thread2并

若从任一目录用什么命令可快速转到用户家目录？

MYSQL查询语句中用表示左然连接。

若关系R满足1NF，且它的每一非主属性完全函数依赖于候

集合与线性表的区别在于是否按关键字排序。

中序遍历平衡的二叉排序树，可得到最后排序的关键码序列。

SQL语言集几个功能模块为一体，其中包括（）

（9 分）某网络拓扑如题 47 图所示，以太网交换机

设(k=a=5,b=3,a*b)，则k值为_____。

设x=4<4-!0，x的值为_____。

有以下程序程序执行后的输出结果是

给定程序中，函数fun的功能是建立一个NxN的矩阵。矩

在 1和 2015之间（包括 1和 2015在内）不能

如果平面上任取 n个整点(横纵坐标都是整数)，其中一定

输入： 2 3 5 7输出： _________

(国王放置 ) 在 n*m 的棋盘上放置 k 个国王，

在下列各项中，只有（）不是计算机存储容量的常用单位。

更多选择题

更多填空题

题量:	0 道
总分:	分

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷