算法：连续邮资问题（回溯+动态规划+剪枝）_回溯算法 剪枝函数

北京工业大学的算法设计与分析课要做个大作业，就选了这个题目。上网找了一些资料，感觉效率有些慢，所以自己又稍微改进了一下。写了好几个版本，不同的实现方法，下面的这个是目前效率最高的。关于两个方向的动态规划的最优子结构性质的证明，如果有疑问的可以邮箱联系hoh_mizukun@163.com。

问题描述

假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，即在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为（1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1－70。

问题分析

对于连续邮资问题，用n元组x[1:n]表示n种不同的邮票面值，并约定它们从小到大排列。x[1]=1是惟一的选择。此时的最大连续邮资区间是[1:m]。x[2]的可取值范围是[2:m+1]。在一般情况下，已选定x[1:i-1]，最大连续邮资区间是[1:r]，则x[i]的可取值范围是[x[i-1]+1:r+1]。

解题思路

由上述的问题分析可知，该问题需要使用深度优先搜索，搜索的对象是每种邮票的面值，第i层对应的是对第i种邮票取值的搜索。从其子结点中找到构成最大连续面值的组合，并与本层结点的面值，共同构成本层结点的结果。
对于搜索过程中的状态，采用二维数组进行存储。C[i][j]表示前i种邮票，构成总面值j时，所需的最少张数，整个搜索的过程就是不断对二维数组进行更新的过程。每次搜索到第n层时，便比较当前邮票组合下的最大连续邮资区间的上限是否大于已搜到结果。若是，则记录该值及对应的邮票面值组合。

int knd = 0;//邮票种类
int lim = 0;//限制张数

int x[NUM];//当前邮票面值
int cnt = 0;//当前邮票种类
int r[NUM];//结果
int max = 0;//最大值

int C[NUM][LEN] = {};//记录搜索结点状态

inline int findMax();//计算当前邮票面值的最大连续邮资区间

void dfs() {
    int tmp = findMax();
    if (cnt == knd) {
  //达到第n层结点，即找到一种可能面值组合
        if (tmp > max) {
  //若比记录的最大连续邮资区间上限大，则更新
            max = tmp;
            for (int i = 1; i <= knd; i++)//记录新的邮票面值组合
                r[i] = x[i];
        }
    }
    else {
        for (int i = x[cnt] + 1; i <= tmp + 1; i++) {
  //下一层结点的面值的可能取值
            x[++cnt] = i;//将可能面值加入当前面值组合中
            dfs();
            cnt--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

findMax()函数的设计

因为findMax()函数在每一个搜索结点中都要调用，所以该函数的效率将直接影响算法的复杂度。
这里为了尽可能少的进行元素的更新，采用了两个方向的DP：
向下DP：若C[i][1]到C[i][j]是前i种邮票构成对应面值所需的最少张数，则可以利用该数据，找到C[i+1][1]到C[i+1][j]对应取值。
向右DP：若C[i][1]到C[i][j]是前i种邮票构成对应面值所需的最少张数，则可以利用该数据，对数组向右进行动态规划，找到其连续邮资区间上限。

为了对该方法有个直观的理解，举例如下所示：
题目：邮票种类3种，邮票张数上限为3

1.第1种邮票的面值一定是1，因为第0种邮票不存在，所以在第一行对面值1的邮票做向右DP，更新的数据为下表中标为粗体的部分。

2.则第2种邮票的面值的取值范围为[2,4],这里先取其面值为2。因为前1种邮票在DP矩阵中已经存在总面值为1到3的数据，所以可以直接利用这些数据，做向下DP，更新的数据为下表中标为粗体的部分。