算法设计与分析课程报告

1、 课程学习报告课程名称：算法分析与设计题 目 求解连续邮资问题 学生姓名 付欢 学生学号 0134355 班 级 计算机131班 开课学期 2015 至 2016 学年 第 一 学期完成时间 2015 年 12 月 23 日目录一问题描述2二问题分析与理解21.连续邮资22.问题1理解分析33.问题2理解分析34.问题3理解分析4三算法设计61.问题1源码62.问题2源码83.问题3源码10四：运行结果12五：总结13一问题描述假设C国共发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。 (约定x1=1)(1)问题1：对给定的面值组合x1,x2,xn，求在信封上贴出金额=R的最

2、少邮票数y。(2)问题2：对给定面值组合x1,x2,xn，求在信封上最多贴m张邮票的前提下，可贴出的连续邮资区间1, maxpos。连续邮资区间是指从1开始的连续正整数，最大到maxpos。(3)问题3：对于给定的n和m值，给出邮票面值的最佳设计。也即x1=?,x2=?,xn=?时使取得的连续邮资区间最大。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。二问题分析与理解1.连续邮资 连续邮资区间1, maxpos,即在最多使用m张邮票的前提下，利用n中给定面值的邮票进行组合可以得到邮资区间1, maxpos的任意一个值。例如，信封

3、上最多允许贴m=4张邮票，现邮局有2种邮票，面值分别为1分、4分，于是可以得到110分和12分、13分、16分邮资，由于得不到11分、14分、15分，所以连续邮资的最大值为maxpos=10，连续邮资区间为1,10。2.问题1理解分析 对于问题1，这是个比较简单的问题，这个问题和我们学程序设计基础时做的“最少硬币问题”所用到的思想和算法是一样的。同样不能使用贪心算法，应该使用动态规划方法。比如，有1分、2分、5分、9分、10分的5种不同面值的邮票，现在需要贴出18分的，按照贪心算法得出的结果就是：10+5+2+1,4种，但这明明是可以用两个9分的。所以可以使用动态规划，要贴出18分时，我们首先

4、找18-1=17，18-2=15，18-5=13，18-9=9，18-10=8；再找17-115-19-1直到得出结果等于0。这样递归解决子问题。这样得出的结果有一个不足之处就是只会输出第一次得出的最佳面额方案。3.问题2理解分析对于问题2，我的想法是先在主函数定义一个max=1，然后调用其他函数看利用这n种邮票能否组合出max，如果能返回1，如果不能则返回0。返回1时使max+，然后再次调用其它函数；返回0时则结束程序的运行，输出这时的max值就是要求的maxpos了。所以首先我得解决的一个重要问题就是在不确定m，n的情况下，利用什么算法能够计算利用这n种邮票在最多使用m张得前提下能组合出的

5、邮资？联系问题1，这个问题就比较简单了，可以使R=max，先求贴出金额为max所需要的最少邮票数y，只要判断y=m是否成立，成立则max+，不成立就输出这个时候的max值。4.问题3理解分析 对于问题3，当我看完这个问题，我第一个想到的是拿比较简单的数据代入，于是我让m=3，n=2。要想连续邮资的区间够大，我第一想到的是邮票面值分别为1分和4分，则在l分-6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；但如果面值分别为1分、3分，则在1分-7分之间的每一个邮资值都能得到。可以验证得当m=3，n2时，7分就是可以得到连续的邮资最大值，所以maxpos=7，面值分别为l分、3分。想到

6、这里，我就想到是不是可以用递推算法，但仔细想想递推是行不通的。这个问题的难点是如何计算最大连续值，一个容易想到的方法是枚举所有的取法，求出可以取到的最大值，再求最大连续值，这样做法比较简单，但实在过于繁琐，而且在主函数中没有确定m，n的值的情况下，其它函数的编写也相当复杂，于是去网上找了一些资料，发现这个问题用回溯法进行解答非常方便，于是从书中找到回溯法这一章节，回溯法是比贪心算法和动态规划算法更一般的方法，它是一种通过搜索状态空间树来求解问题的可行解和最优解的方法。通过对回溯法的了解，发现这个问题就是应该使用回溯法来解答。首先，搜索结点的状态应该是已经确定的邮票面值(各不相同并且总数不超过n

7、)和它们能够贴出的最大连续邮资区间，以此来枚举下一个可能的邮票面值。因此，很自然地，使用书中的标识符，数组x记录当前已经确定的邮票面值，整数r表示当前使用不超过m张邮票能贴出的最大连续邮资区间。对于第i层的结点，x1i表示当前已经有i个面值确定，r表示由x1i能贴出的最大连续区间，现在，要想把第i层的结点往下扩展，有两个问题需要解决：一，哪些数有可能成为下一个的邮票面值，即xi+1的取值范围是什么；二，对于一个确定的xi+1，如何更新r的值让它表示x1i+1能表示的最大连续邮资区间。第一个问题比较简单，xi+1的取值要和前面i个数各不相同，最小应该是xi + 1，最大就是r+1，否则r+1没有

8、办法表示。第二个问题我认为应该计算出所有使用不超过m张x1i+1中的面值能够贴出的邮资，然后从r+1开始逐个检查是否被计算出来。这个计算量是非常巨大的，需要用到动态规划算法，假设S(i)表示x1i中不超过m张邮票的贴法的集合，定义S(i)中元素的值就是它所表示的贴法贴出来的邮资，于是，可以把S(i)中的元素按照它们的值的相等关系分成k类。第j类表示贴出邮资为j的所有的贴法集合，用T(j)表示，T(j)有可能是空集，例如对于1,4,T(7)为空集，T(8)=4,4。此时有：S(i) = T(1) U T(2) U T(3) U U T(k)。现在考虑xi+1加入后对当前状态S(i)的影响。假设s

9、是S(i)中的一个元素，即s表示一种合法的贴法，xi+1对s的影响就是，如果s中贴的邮票不满m张，那就一直贴xi+1，直到s中有m张邮票，这个过程会产生出很多不同的邮资，它们都应该被加入到S(i+1)中，因为s属于S(i)，它也必定在某个T(k)中，而T(k)中能产生出最多不同邮资的是T(k)中用的邮票最少的那个元素。用数组x记录邮票面值，用r表示当前当前已经确定最大的连续邮资区间，用数组y表示用当前的面值贴出某个邮资所需要的最少的邮票数，再加上状态结点的转换过程，就可以利用回溯法求解了。三算法设计（1）问题1源码：对给定的面值组合x1,x2,xn，求在信封上贴出金额=R的最少邮票数y。#in

10、cludeint x999;using namespace std; void FindMin(int R,int *x, int n, int m) int *xNum=new intR+1();/贴出金额R最少需要的邮票的数量 int *xValue=new intR+1();/最后加入的邮票，方便后面输出是哪几个邮票 xNum0=0; for(int i=1;i=R;i+) int minNum=i;/i面值邮票，需要最少邮票个数 int usedR=0;/这次贴，在原来的基础上需要的邮票 for(int j=0;j=xj)/贴的金额大于这个邮票的面值 if(xNumi-xj+1m) c

11、out不能贴出所需金额的邮票endl; else cout需要最少邮票数为：xNumRendl; cout0) coutxValueR,; R-=xValueR; delete xNum; delete xValue; int main()int R,i,n,m;printf(请输入最多贴的邮票数m：);scanf(%d,&m);printf(请输入要贴出的金额R：);scanf(%d,&R);printf(请输入发行的邮票种类n：);scanf(%d,&n);printf(请输入发行的%d种邮票的面额：,n);for(i=0;in;i+)scanf(%d,&xi); FindMin(R,x,

12、n,m);(2)问题2源码：对给定面值组合x1,x2,xn，求在信封上最多贴m张邮票的前提下，可贴出的连续邮资区间1, maxpos。连续邮资区间是指从1开始的连续正整数，最大到maxpos。#includeint x999;using namespace std; int maxpos(int R,int *x, int n, int m) int *xNum=new intR+1();/贴出金额R最少需要的邮票的数量 int *xValue=new intR+1();/最后加入的邮票，方便后面输出是哪几个邮票 xNum0=0; for(int i=1;i=R;i+) int minNum=

13、i;/i面值邮票，需要最少邮票个数 int usedR=0;/这次贴，在原来的基础上需要的邮票 for(int j=0;j=xj)/贴的金额大于这个邮票的面值 if(xNumi-xj+1m) return 0; else return 1; delete xNum; delete xValue; int main()int max=1;int i,n,m;printf(请输入最多贴的邮票数m：);scanf(%d,&m);printf(请输入发行的邮票种类n：);scanf(%d,&n);printf(请输入发行的%d种邮票的面额：,n);for(i=0;in;i+)scanf(%d,&xi)

14、; while(1) if(maxpos(max,x,n,m) max+; else break; printf(The maxpos is %d.n,max-1); (3)问题3源码：对于给定的n和m值，给出邮票面值的最佳设计。也即x1=?,x2=?,xn=?时使取得的连续邮资区间最大。#includeusing namespace std;class Stampfriend int MaxStamp(int ,int ,int );private: int Bound(int i); void Backtrack(int i,int r); int n;/邮票面值数 int m;/每张信封

15、最多允许贴的邮票数 int maxvalue;/当前最优值 int maxint;/最大整数 int maxl;/邮资上界 int *x;/当前解 int *y;/贴出各种邮资所需最少邮票数 int *bestx;/当前最优解;int MaxStamp(int n,int m,int bestx)Stamp X;int maxint=99999;int maxl=9999;X.n=n;X.m=m;X.maxvalue=0;X.maxint=maxint;X.maxl=maxl;X.bestx=bestx;X.x=new int n+1;X.y=new int maxl+1;for(int i=

16、0;i=n;i+)X.xi=0;for(i=1;i=maxl;i+)X.yi=maxint;X.x1=1;X.y0=0;X.Backtrack(2,1);printf(当前最优解: );for(i=1;i=n;i+)coutbestxi ;coutendl;delete X.x;delete X.y;return X.maxvalue;void Stamp:Backtrack(int i,int r)for(int j=0;j=xi-2*(m-1);j+)if(yjm)for(int k=1;k=m-yj;k+)if(yj+kyj+xi-1*k)yj+xi-1*k=yj+k;while(yrn

17、)if(r-1maxvalue)maxvalue=r-1;for(int j=1;j=n;j+)bestxj=xj;return;int *z=new intmaxl+1;for(int k=1;k=maxl;k+)zk=yk;for(j=xi-1+1;j=r;j+)xi=j;Backtrack(i+1,r);for(int k=1;k=maxl;k+)yk=zk;delete z;void main()int *bestx;int n;int m;printf(请输入邮票种类数n: );scanf(%d,&n);printf(请输入每张信封最多允许贴的邮票数m: );scanf(%d,&m);bestx=new intn+1;for(int i=1;i=n;i+)bestxi=0;cout最大邮资区间为: 1到MaxStamp(n,m,bestx)endl;四：运行结果(1) 问题1程序运行结果演示如下图：（由于凑出80的至少需要8张面额为10的，超出最多贴的邮票数5，故输出不能贴出所需金额的邮票） (2) 问题2程序运行结果演示如下图：(3) 问题3程序运行结果演示如下图：五：总结 在求解连续邮资的问题中，我主要运用了算法设计与分析中的动态规划法和回溯法，深入了解了贪心算法、动态规划算法以及回溯算法在这个连续邮资的问题上的优缺点，学会对待不同的问题如何去选择更优的算法