转载自:http://blog.csdn.net/jcwkyl/article/details/4137398 By jcwKyl
王晓东老师编著的《计算机算法设计与分析》5.12节以“连续邮资问题”为例展示了回溯法的应用。讲解比较简略,对于搜索出一张新的邮票面值后如何更新最大连续邮资区间这一点没有过多的说明。以下是自己对于这一节学习的一点笔记。
实际上,关于刚才所说的更新最大连续邮资区间的方法,可以归结到一种“等价类”的思想。与此相似的还有《编程之美》中“数组分割问题”的解法三,《编程之美》中“找符合条件的整数”的最后一种算法,JOJ
1903,JOJ 1278这些题目等等。以下先从头到尾把连续邮资问题复习一遍,然后小结一下这种“等价类”的方法。
连续邮资问题:某国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,在1张信封上贴出从邮资1开始,增量为1的最大连续邮资区间。例如,当n=5和m=4时,面值为{1,3,11,15,32}的5种邮票可以贴出的最大连续邮资区间是1到70.
当然是用回溯法。搜索结点的状态应该是已经确定的邮票面值(各不相同并且总数不超过n)和它们能够贴出的最大连续邮资区间,以此来枚举下一个可能的邮票面值。因此,很自然地,使用原书中的标识符,数组x记录当前已经确定的邮票面值,整数r表示当前使用不超过m张邮票能贴出的最大连续邮资区间。对于第i层的结点,x[1…i]表示当前已经有i个面值确定,r表示由x[1…i]能贴出的最大连续区间,现在,要想把第i层的结点往下扩展,有两个问题需要解决:一,哪些数有可能成为下一个的邮票面值,即x[i+1]的取值范围是什么;二,对于一个确定的x[i+1],如何更新r的值让它表示x[1…i+1]能表示的最大连续邮资区间。~
第一个问题很简单,x[i+1]的取值要和前面i个数各不相同,最小应该是x[i]
+ 1,最大就是r+1,否则r+1没有办法表示。我们现在专注第二个问题。
第二个问题自己有两种思路:一,计算出所有使用不超过m张x[1…i+1]中的面值能够贴出的邮资,然后从r+1开始逐个检查是否被计算出来。二,从r+1开始,逐个询问它是不是可以用不超过m张x[1…i+1]中的面值贴出来。
两种思路直接计算其计算量都是巨大的,需要借助动态规划的方法。模仿0-1背包问题,假设S(i)表示x[1…i]中不超过m张邮票的贴法的集合,这个集合中的元素数目是巨大的,例如,只使用1张邮票的贴法有C(i+1-1,1)=C(i,1)=i种,使用2张邮票的贴法有C(i+2-1,2)=C(i+1,2)=i*(i+1)/2种,……,使用m张邮票的贴法有C(i+m-1,
m)种,其中C(n,r)表示n个元素中取r个元素的组合数。于是,S(i)中的元素的数目总共有C(i+1-1,
1) + C(i+2-1,2)+ … + C(i+m-1,m)个。S(i)中的每个元素就是一种合法的贴法,对应一个邮资。当前最大连续邮资区间为1到r,那么S(i)中每个元素的邮资是不是也在1到r之间呢?不一定,比如{1,2,4},当m=2时,它能贴出来8,但不能贴出来7,这一点自己在写代码时犯了错误。总之,在搜索时,一定要保持状态的一致性,即当深度搜索到第i层时,一定要确保用来保存结点状态的变量中保存的一定是第i层的这个结点的状态。言归正传,定义S(i)中元素的值就是它所表示的贴法贴出来的邮资,于是,可以把S(i)中的元素按照它们的值的相等关系分成k类。第j类表示贴出邮资为j的所有的贴法集合,用T(j)表示,T(j)有可能是空集,例如对于{1,2,4},T(7)为空集,T(8)={{4,4}}。此时有:S(i)
= T(1) U T(2) U T(3) U … U T(k),U表示两个集合的并。
现在考虑x[i+1]加入后对当前状态S(i)的影响。假设s是S(i)中的一个元素,即s表示一种合法的贴法,x[i+1]对s能贴出的邮资的影响就是x[i+1]的多次重复增加了s能贴出的邮资。这样说是因为有两种情况不需要考虑:一, 从s中去掉几张邮票,把x[i+1]加进去,这没有意义,因为从s中去掉几张邮票后s就变成了S(i)中的另一个元素t,我们迟早会对t考虑x[i+1]的影响的。二,将x[i+1]加入s,同时再把x[1]也加入s(如果s中还能再贴两张邮票的话),这也没有意义,原因同一。所以,x[i+1]对s的影响就是,如果s中贴的邮票不满m张,那就一直贴x[i+1],直到s中有m张邮票,这个过程会产生出很多不同的邮资,它们都应该被加入到S(i+1)中。因为s属于S(i),它也必定在某个T(k)中,而T(k)中能产生出最多不同邮资的是T(k)中用的邮票最少的那个元素。至此,原书中的解法就完全出来了:用数组x记录当前已经确定的邮票面值,用r表示当前最大的连续邮资区间,用数组y表示用当前的面值贴出某个邮资所需要的最少的邮票数。状态结点的转换过程已经在上面说的非常清楚了。现在只差写代码了。
代码如下:
#include<stdio.h>
#defineMAX_NM 10
#defineMAX_POSTAGE 1024
#defineINF 2147483647
intn,
m;
intx[MAX_NM],ans[MAX_NM],
y[MAX_POSTAGE],maxStamp, r;
/*
* backtrack(i)表示x[0...i-1]这i张邮票已经完全确定,
*相应于x[0...i-1]的最大连续邮资区间r和每种邮资所需要的
*最少邮票张数y[0...r]也都确定,现在枚举x[i]
*的每个值,确定x[i]
*/
voidbacktrack(inti)
{
int*backup_y,backup_r;
intnext,
postage, num,tmp;
if(i>=
n) {
if(r
>maxStamp) {
maxStamp= r;
for(tmp=
0;tmp< n;tmp++)
ans[tmp] = x[tmp];
}
return;
}
backup_y= (int*)malloc(MAX_POSTAGE
*sizeof(int));
for(tmp=
0;tmp< MAX_POSTAGE;tmp++)backup_y[tmp] = y[tmp];
backup_r= r;
for(next
= x[i- 1] + 1; next <= r + 1; next++) {
/* update x[i]
*/
x[i] = next;
/* update y */
for(postage
= 0; postage < x[i-1] * m; postage++) {
if(y[postage]
>= m)continue;
for(num
= 1; num <= m - y[postage]; num++)
if(y[postage]
+ num < y[postage + num * next]
&& (postage + num * next < MAX_POSTAGE))
y[postage + num * next] = y[postage] + num;
}
/* update r */
while(y[r
+ 1] < INF) r++;
backtrack(i+ 1);
/* restore */
r =backup_r;
for(tmp=
0;tmp< MAX_POSTAGE;tmp++) y[tmp] =backup_y[tmp];
}
free(backup_y);
}
intmain()
{
inti;
scanf("%d%d",
&n, &m);
x[0] = 1;
r = m;
for(i=
0;i<= r;i++) y[i] =i;
while(i<
MAX_POSTAGE) y[i++] = INF;
maxStamp= 0;
backtrack(1);
printf("max
stamp is: %d/n",maxStamp);
for(i=
0;i< n;i++)printf("%4d",ans[i]);
return0;
}
用算法教材上的蒙特卡罗方法估算该算法解空间树的结点数,得到以下结果:
n
|
m
|
解
|
平均结点数
|
5
|
4
|
{1,3,11,15,32}:70
|
6190
|
5
|
5
|
{1,4,9,31,51}:126
|
26762
|
5
|
6
|
{1,7,12,43,52}:216
|
94690
|
6
|
3
|
{1,3,7,9,19,24}:52
|
12587
|
6
|
4
|
{1,4,9,16,38,49}:108
|
158364
|
分享到:
相关推荐
连续邮资问题是一种经典的组合优化问题,常出现在算法设计与分析的课程中。该问题源自于邮寄包裹时如何使用不同面额的邮票最高效地凑出所需邮资。在这个问题中,假设我们有一系列固定面额的邮票,目标是找出最少数量...
"邮资计价器"是一款实用的小型软件,专门用于计算邮寄信函所需的邮资费用。在使用这款软件时,用户需要有一台秤来测量信函的重量,然后将重量输入到软件中,软件会自动根据当前邮政服务的收费标准来计算出准确的邮资...
实验任务多样,涉及矩阵链相乘问题、投资问题、背包问题、旅行商问题(TSP)、数字三角形、哈夫曼编码、顾客等待时间最短问题、最小生成树问题、图着色问题、八皇后问题、连续邮资问题、卫兵布置问题、圆排列问题、...
本文主要探讨了三个经典的算法问题:韩罗塔问题、连续邮资问题和棋盘覆盖问题与矩阵链乘问题,它们都是算法分析与设计中的重要实例。我们将分别对这三个问题进行深入的解析和讨论。 首先,我们来看韩罗塔问题。这是...
如装载问题、批处理作业调度、符号三角形问题、n后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题以及连续邮资问题,这些都是回溯法常用于求解的经典问题。这些问题的...
回溯法常用于解决各种问题,如装载问题、批处理作业调度、符号三角形问题、n皇后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题和连续邮资问题等。这些问题通常具有...
#### 连续邮资问题 **知识点:** 1. **邮票组合问题:** 需要找到最佳的邮票面值设计,使得可以组合出连续的邮资。 2. **动态规划算法:** 使用动态规划算法来解决问题,寻找最优解。 3. **状态转移方程:** 定义...
回溯法常用于解决一系列经典问题,如装载问题、批处理作业调度、符号三角形问题、n皇后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题以及连续邮资问题等。这些问题...
回溯法常用于解决如装载问题、批处理作业调度、符号三角形问题、n皇后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题和连续邮资问题等。这些问题通常具有大量的可能性...
- **连续邮资问题:** 连续邮资问题。 #### 二、概念题解析 **2.1 递归的概念** 递归算法是一种能够直接或间接调用自身的算法。递归函数通过定义自身来解决问题。 **2.2 0-1背包问题** 0-1背包问题是一个经典的...
在实际应用中,回溯法常被用于解决一系列问题,如装载问题、批处理作业调度、符号三角形问题、n皇后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题以及连续邮资问题等...
4. **应用范例**:回溯法广泛应用于多个领域,包括装载问题、作业调度、符号三角形问题、n皇后问题、0-1背包问题、最大团问题、图的着色问题、旅行售货员问题、圆排列问题、电路板排列问题以及连续邮资问题等。...
回溯法是一种重要的算法策略,尤其适用于解决组合优化问题,如0-1背包问题、n皇后问题、子集和数问题、图的着色问题、旅行商问题(TSP)和连续邮资问题等。回溯法的核心在于深度优先搜索(DFS),它以递归的方式在解...
连续邮资问题)。 回溯法是一种搜索算法,旨在解决问题的解空间树。回溯法可以解决许多问题,如 n 皇后问题、装载问题、批量作业调度等。 28. 分支定界法类似于回溯法。它也是一种在解空间树 T 上搜索问题解的算法...
##### (6)连续邮资问题 **问题描述**:给定n种不同面值的邮票和每张信封上最多允许贴m张邮票,求出能够组成的连续邮资的最大长度。 **算法思路**: - 使用动态规划方法求解。 - 定义状态转移方程,根据邮票面值...
3. **连续邮资问题**:涉及组合数学和动态规划,如何用有限种类面额的邮票凑出所有可能的总价值。 4. **找第k大的数**:可以使用快速选择或优先队列(堆)来解决,快速找到数组中第k大的元素。 5. **矩阵中的数字*...
12. **回溯法**:深度优先搜索策略,用于解决约束满足问题,如连续邮资问题,解空间以树形结构表示。 13. **分支限界法**:广度优先或最小耗费优先搜索,每个节点只有一 次机会成为活节点,如堆排序在最小耗费优先...