算法设想与分析尝试 （持续邮资题目）

fck1956272

来历：知乎
1、尝试情况

         VisualC++ 6.0
2、尝试目标和要求

l  尝试方针：操纵回溯法求解持续邮资题目。
l  尝试内容：
Ø  假定国家刊行了n种分歧面值的邮票，而且规定每张信封上最多只答应贴m张邮票。
l  尝试要求：
Ø  持续邮资题目要求对于给定的n和m的值，给出邮票面值的最好设想，在1张信封上可贴出从邮资1起头，增量为1的最大持续邮资区间。
l  当n=2、m=3时：
Ø  假如面值别离为1、4，则在1-6之间的每一个邮资都能获得（固然还有8、9和12）；
Ø  假如面值别离为1、3，则在1-7之间的每一个邮资都能获得；
l  当n=5、m=4时：
Ø  面值为（1,3,11,15,32）的五种邮票可以贴出邮资的最大邮资区间是1到70.
3、解题思绪、伪代码

3.1解题思绪
（1）先从简单动手，若前cur张邮票面值已经肯定，若何判定由这些面值,在张数不跨越m的情况下能否贴出该邮资re。很轻易想到，这是一个类似背包题目，可采用用回溯法求解。
checkanser(temp,cur,re,m,num)
其中：
temp数组：记录已经肯定下来的面值
cur:当前已经肯定的面值数目
re:当前需要贴出的邮资
m:信封最多答应贴m张邮票
num:已经张贴的邮票数目
1、向信封上贴第一张邮票，可以有cur种挑选，被挑选了第i张面值时，题目缩小为：
前cur张邮票面值已经肯定，若何判定由这些面值,在张数不跨越m的情况下能否贴出该邮资re-temp.
即：checkanser(temp,cur,re-temp[j],m,num+1)
2、当re=0时，算法竣事，暗示由已肯定下来的邮票，可以在满足条件的情况下，贴出邮资为re.
3、当re=1时，暗示当前贴法没法贴出邮资re,则挑选贴下一张邮票，若一切的邮票都不满足要求，向前回溯。
4、约束条件：已经张贴的邮票数目num不得跨越m
（2）判定由已选的面值,在张数不跨越m的情况下能贴出的最大邮资
即从小能到大依次持续列举邮资，挪用（1）判定该邮资能否获得，从而得出最大持续邮资。
（3）已经拔取到第cur种面值邮票,肯定下一张面值
若前cur张面值为temp[cur],最大能贴出的最大持续邮资为max，明显下一张面值的能够取值只能够在temp[cur]+1到
max+1当中。由于前面的邮票的面值会影响前面面值能，如n=3,m=4时，最优面值为（1,5,8）;n=4,m=4时，最优面值为：（1，3，11，18），是以，该题目不具有无后向性，不是一个贪心题目。因而采用dfs搜索算法停止求解，dfs树的每一个叶子代表能够的面值，每一条从根到叶子的途径暗示一组满足条件的解。最初从一切满足条件的解当选出最优解。
代码

1. #include <stdio.h>
3. #include <string.h>
5. int n;//n种面值
7. int m;//最多答应贴m张
9. int result[100];//终极成果
11. int temp[100];//暂存各类能够成果
13. int maxRe=0;//最大邮资
15. int checkanser(int temp[],int
16. cur,int re,int m,int num);
18. void getNext(int temp[],int
19. cur,int max,int m);
21. int maxl(int temp[],int
22. cur,int m,int max);
24. //判定由已选的面值,在张数不跨越m的情况下能否贴出该邮资re
26. //回溯法判定
28. int checkanser(int temp[],int
29. cur,int re,int m,int num)//cur:当前已经肯定的面值数目num:已经张贴的邮票数目
31. {   
33.     if(re==0)
35.         return 1;
37.     if(re<0)
39.         return 0;
41.     for(int j=cur;j>=1;j--)
43.     {
45.         if(num<m)
47.         {
49.             num++;
51.             if(checkanser(temp,cur,re-temp[j],m,num)==1)//利用了第i个面值的邮票
53.             {
55.                 return 1;
57.             }else
59.             {
61.                 num--;//规复现场
63.             }
65.         }
67.     }
69.     return 0;
71. }
73. //判定由已选的面值,在张数不跨越m的情况下能贴出的最大邮资
75. int maxl(int temp[],int
76. cur,int m,int max)
78. {
80.     for(int k=max+1;k<m*temp[cur];k++)
82.     {
84.         if(checkanser(temp,cur,k,m,0)==0)
86.             break;
88.     }
90.     return k-1;
92. }
94. void getNext(int temp[],int
95. cur,int max,int m)//cur:已经拔取到第cur种邮票,肯定下一张面值
97. {
99.     if(cur==n)//遍历到叶子
101.     {
103.         if(maxRe<max)
105.         {
107.             maxRe=max;
109.             for(int z=1;z<=n;z++)
111.             {
113.                 result[z]=temp[z];
115.             }
117.         }
119.         return;
121.     }
123.     for(int k=temp[cur]+1;k<=max+1;k++)
125.     {
127.         temp[cur+1]=k;
129.         int max1=maxl(temp,cur+1,m,max);//下一个面值取k时能到达的最大邮资
131.         if(max1>max)//k可取
133.         {
135.             getNext(temp,cur+1,max1,m);//继续递归肯定接下来的面值
137.         }
139.     }
141. }
143. int main()
145. {
147.     printf("请输入面值数目(n)：\n");
149.     scanf("%d",&n);
151.     printf("请输入每张信封最多答应贴的邮票数目(m)：\n");
153.     scanf("%d",&m);
155.     temp[1]=1;
157.     getNext(temp,1,m,m);
159.     printf("\n邮票面值别离为：");
161.     for(int i=1;i<=n;i++)
163.     {
165.         printf("%d ",result[i]);
167.     }
169.     printf("\n最大邮资区间为：1-%d\n",maxRe);
171.     return 0;
173. }

复制代码

4、尝试步调

4.1输入



4.2输出：



5、会商和分析

对算法及尝试成果停止分析会商。

• 尝试成果分析:
  

  经历证当输入n=5,m=4情况下
  最大邮资区间为1-70
  考证建立。
总结：

1 当碰到算法题目时，要先判定它属于什么范例的题目。由于前面的邮票的面值会影响前面面值能，如n=3,m=4时，最优面值为（1,5,8）;n=4,m=4时，最优面值为：（1，3，11，18），是以，该题目不具有无后向性，不是一个贪心题目。
2 利用回溯法时要留意规复现场，肯定鸿沟条件和回溯的条件，才能经过回溯获得正确的成果。

原文地址：https://zhuanlan.zhihu.com/p/482100107
免责声明：本帖内容由机械人自动收集于互联网，如加害了您的权益，请联系我们【E-Mail:cb@yoyodoc.com】 我们会实时删除侵权内容，给您带来未便，深感歉意！