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

其它题目

在语句cout<<'A';中，cout是

（本题 8 分）某系统中进程的虚拟地址空间包括内核区、

请编写函数fun，其功能是：计算并输出3到n之间（含3

一棵二叉树的前序遍历结果是ABCEDF，中序遍历结果是

设有定义：以下不能计算出一个char型数据所占字节

设有定义：以下不能完整输出变量x值的语句是（）。

有以下定义：以下叙述中错误的是。

有以下程序：程序的运行结果是。

有以下程序：程序运行后的输出结果是。

同一个列表对象中的元素类型可以各不相同。

表达式sorted({'a':3,'b':9,'c':

设int *ptr,x,array[5]={5,4,3

在C语言源程序中，一个变量代表___________。

以下程序的功能是

以下程序的功能是：借助指针变量找出数组元素中最大值所在

以下叙述中不正确的是（）。

拟建设一个光通信骨干网络连通BJ、CS、XA、QD、J

在UNIX/Linux系统中，环境变量是非常重要，在字

shell不仅是（），它同时也是一种功能强大的编程语

创建表的语句中，unique key子句表示定义唯一约

有n个叶子的哈夫曼树的结点总数为

路由器的路由表包括目的地址、下一站地址以及

（8 分）假设计算机 M 的主存地址为 24 位，按字

若某主机的 IP 地址是 183.80.72.48，子

C语言中，数组名是一个不可变的_____量，不能对它进

#define和printf都不是C语句。

设x和y均为int型变量，则以下for循环中的scan

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

有如下程序段：当执行上述程序段，并从键盘输入：name

一个 1×8的方格图形（不可旋转）用黑、白两种颜色填涂

更多选择题

更多填空题

题量:	0 道
总分:	分

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

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

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷