算法:连续邮资问题(回溯+动态规划+剪枝) | 您所在的位置:网站首页 › 8种最美信封折法 › 算法:连续邮资问题(回溯+动态规划+剪枝) |
问题描述
假设国家发行了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层时,便比较当前邮票组合下的最大连续邮资区间的上限是否大于已搜到结果。若是,则记录该值及对应的邮票面值组合。 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,更新的数据为下表中标为粗体的部分。
一种可行的剪枝方法 记邮票种类为m,张数限制为n,使用回溯法不断更新的最大连续邮资区间上限为max。 则在遍历第m种邮票的面值时,若x[m]*n |
CopyRight 2018-2019 实验室设备网 版权所有 |