连续邮资问题

article/2025/10/8 7:22:23

1、实验环境

Visual C++ 6.0

2、实验目的和要求

利用回溯法解决连续邮资问题。假设某国家发行了n种不同面值的邮票并且规定每张信封上最多只允许贴m张。对于给定的n和m的值，给出邮票面值的最佳设计，使得可在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。

3、解题思路、伪代码

3.1解题思路

（1）对于连续邮资的问题，由于实验开始是仅给出面值的数量，而面值的具体值是未知的。但是由于邮资需要从1开始，因此，面值具体值中必然有1。可以建立一个数组用于存储具体的面值。X[1:n]表示从小到大存储具体面值。

（2）当面值为1时，可形成的连续邮资区间为1~m，在此基础上，若要增加面值，为保证区间连续，第二个面值必然要在2~m+1中取（第二个面值不能为1，并且若为m+2或者更大时，只用一个就变为m+2，此时不连续），第三个面值则需要根据前两个面值能达到的最大值来确定。第i个面值x[i]的连续区间若为1~r时，则第x[i+1]的个的取值必然为x[i]+1到r+1。则从第一个面值开始，接下来的各个面值的取值都由上一个面值以及能形成的最大值来取。

（3）但是为了求解最大连续区间，需要将面值的所有情况进行考虑，则对面值可能取值的语法树进行递归遍历，即回溯。递归到叶子节点时，将当前情况的最大值进行记录并与之前的进行比较，若更大则保存最大值，之后回溯到上一层继续求解，直到将所有情况计算完成。

（4）为在第n层得到最大连续邮资区间，则在前几层进行计算，必须要达到即保证连续，又要保证每个邮资值尽量使用比较少的邮票张数，即多使用邮资大的邮票。这就要求每引进一个新的邮票的时候，需要对当前邮资值数组进行更新，以保证每个邮资值的达到使用的是最少的邮票数。

回溯法按深度优先策略搜索问题的解空间树（问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根节点到当前节点的路径）。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：

使用约束函数，剪去不满足约束条件的路径；
使用限界函数，剪去不能得到最优解的路径。

这种方法常常可以避免搜索所有可能的解，适用于求解组合数组较大的问题，在此问题中遍历确实可以得到问题的解，不过效率非常低，用回溯法可以有效地优化算法。

回溯法求解的三个步骤

1.针对问题，定义问题的解空间

2.确定容易搜索的解空间结构

3.以深度优先方式搜索解空间，并在搜索过程中用剪纸函数避免无效的搜索结果

3.2伪代码

#include<stdio.h>

#define maxl 1000    //表示最大连续值

#define maxint 32767

int n,m;      //n为邮票种类数，m为能贴的最大张数

int maxvalue;      //表示最大连续值

int bestx[100];     //表示最优解

int y[maxl];     //y[k]，存储表示到k值，所使用的最少邮票数

int x[100];      //存储当前解

void backtrace(int i,int r);

int main(){

printf("请输入邮票面值数：");

scanf("%d",&n);

printf("请输入能张贴邮票的最大张数：");

scanf("%d",&m);

for(int i=0;i<=n;i++){

  x[i]=0;

  bestx[i]=0;

}

for(int i=0;i<maxl;i++){

  y[i]=maxint;

}

x[1]=1;

y[0]=0;

maxvalue=0;

backtrace(1,0);

printf("当前最优解为：");

for(int i=1;i<=n;i++){

  printf("%d ",bestx[i]);

}

printf("\n最大连续邮资为：");

printf("%d",maxvalue);

return 1;

}

void backtrace(int i,int r){

for(int j=0;j<=x[i-1]*m;j++){    //对上一层的邮资值数组进行更新，上限是x[i-1]*m

  if(y[j]<m){

   for(int k=1;k<=m-y[j];k++){   //从只使用一个x[i]到使用m-y[i]个，即使用最多的最大值，降低邮票数

    if(y[j]+k<y[j+x[i]*k]){

     y[j+x[i]*k]=y[j]+k;   //如果前面的某一个情况加上k个x[i]，所达到邮资值使用的邮票数少于原来的邮票数则更新

    }

   }

  }

}

while(y[r]<maxint){       //向后寻找最大邮资值

  r++;

}

if(i==n){         //i=n表示到达叶子节点。

  if(r-1>maxvalue){      //若大于最大值，则更新最优值与最优解

   for(int k=1;k<=n;k++){

    bestx[k]=x[k];

   }

   maxvalue = r-1;

  }

  return;

}

int z[maxl];

for(int k=0;k<maxl;k++){     //由于每一层需要对多种情况进行运算，因此需要将上一层的邮资值数组保留

  z[k] = y[k];

}

for(int j=x[i]+1;j<=r;j++){     //对下一层进行运算

  x[i+1]=j;

  backtrace(i+1,r-1);

  for(int k=0;k<maxl;k++)

   y[k]=z[k];

}

}

4、实验步骤

4.1输入：

2,3

5,4

4,3

4.2输出：

源码，取用点赞谢谢

#include<stdio.h>
#define maxl 1000    //表示最大连续值 
#define maxint 32767
int n,m;      //n为邮票种类数，m为能贴的最大张数 
int maxvalue;      //表示最大连续值
int bestx[100];     //表示最优解
int y[maxl];     //y[k]，存储表示到k值，所使用的最少邮票数 
int x[100];      //存储当前解 
void backtrace(int i,int r);int main(){printf("请输入邮票面值数：");scanf("%d",&n);printf("请输入能张贴邮票的最大张数：");scanf("%d",&m);for(int i=0;i<=n;i++){x[i]=0;bestx[i]=0;} for(int i=0;i<maxl;i++){y[i]=maxint;}x[1]=1;y[0]=0;maxvalue=0;backtrace(1,0);printf("当前最优解为：");for(int i=1;i<=n;i++){printf("%d ",bestx[i]);} printf("\n最大连续邮资为：");printf("%d",maxvalue);return 1;
} void backtrace(int i,int r){for(int j=0;j<=x[i-1]*m;j++){    //对上一层的邮资值数组进行更新，上限是x[i-1]*m if(y[j]<m){for(int k=1;k<=m-y[j];k++){   //从只使用一个x[i]到使用m-y[i]个，即使用最多的最大值，降低邮票数 if(y[j]+k<y[j+x[i]*k]){y[j+x[i]*k]=y[j]+k;   //如果前面的某一个情况加上k个x[i]，所达到邮资值使用的邮票数少于原来的邮票数则更新 }}}}while(y[r]<maxint){       //向后寻找最大邮资值 r++;}if(i==n){         //i=n表示到达叶子节点。 if(r-1>maxvalue){      //若大于最大值，则更新最优值与最优解 for(int k=1;k<=n;k++){bestx[k]=x[k];    }maxvalue = r-1;}return;}int z[maxl];for(int k=0;k<maxl;k++){     //由于每一层需要对多种情况进行运算，因此需要将上一层的邮资值数组保留 z[k] = y[k];}for(int j=x[i]+1;j<=r;j++){     //对下一层进行运算 x[i+1]=j;backtrace(i+1,r-1);for(int k=0;k<maxl;k++)y[k]=z[k];}
}