邮票问题递推

【问题描述】
设有已知面额的邮票m种，每种有n张，用总数不超过n张的邮票，能从面额1开始，最多连续组成多少面额。（1≤m≤100，1≤n≤100，1≤邮票面额≤255）
【输入格式】
第一行：m,n的值，中间用一空格隔开。
第二行：A[1..m]（面额），每个数中间用一空格隔开。
【输出格式】
连续面额数的最大值
【输入样例】stamp.in
3 4
1 2 4
【输出样例】stamp.out
14

using namespace std; int n,m,i,j,k; int c[256]; //面额 int a[31001]; //递推数组 bool b1; void readfile()//读入数据 { cin >> m >> n; b1 = true; for (i = 1; i <= m; i++) { cin >> c[i]; if (c[i] == 1) b1 = false; } } 　void work() { if (b1 == true) cout << "MAX=0"; //不存在面额1时输出无解 else { i = 1; a[i] = 1; do { i++; for (j = 1; j <= m; j++) if (((i % c[j] == 0) && ((i / c[j]) < a[i])) || (a[i] == 0)) a[i] = i / c[j]; //判断它能否被题目给定面额整除 for (j = 1; j <= i/2; j++) if (a[j] + a[i-j] < a[i]) a[i] = a[j] + a[i-j]; //寻找(1<=j<=i),使a[j]+a[i-j]值最小 } while ((a[i] <= n) && (a[i] != 0)); cout << i-1; //输出 } } int main ( ) { readfile() ; work(); return 0; }

【算法分析】
一看到这个题目，给人的第一感觉是用回溯算法，从面额1开始，每种面额都用回溯进行判断，算法复杂度并不高，但是当m，n取到极限值100时，程序明显超时，因此，回溯算法在这里并不可取。能否用递推完成呢?我们有一个思路:从面额1开始，建立递推关系方程，就用范例来说吧，面额1，2，4只用1张邮票行了，面额3可以表示为面额1，2的邮票和1+1=2，面额5有两种表示方式min(面额1+面额4，面额2+面额3)，照此类推，递推关系方程不难建立，就拿邮票问题来说，以下是递推的一种方法:
【邮票问题】这种递推方法虽然简单，由于1<=邮票面额<=255，1<=n<=100，因此MAX值最多可达到25500，25500次循环里必定还有嵌套循环，因此算法不加优化，很难在规定时间内得出最优值。这就需要递推的算法优化。一味递推不寻求算法优化，速度较之搜索提高不少，但一旦数据规模过大，很难在规定时间内得出最优值。这种递推方法原理是:对于某种要求得到的面额，判断它能否被题目给定面额整除，再寻找(1<=j<=i)，使A[j]+A[i-j]值最小，求出凑成某种面额最少邮票数，算法虽然简单，但还可以进一步优化。何不将用m种面额邮票作循环，建立递推关系式:A[i]=MAX(A[I-C[j]]+1)，于是当取到极限值时，程序减少了约1.6*10^8次循环，递推优化作用不言而喻。

下面是改进后的程序: #include #include using namespace std; int x[256]; int pieces[30001]; int m,n,i,j; int main() { cin >> m >> n; for (i = 1; i <= m; i++) cin >> x[i]; memset(pieces,0,sizeof(pieces)); int maxx = 0; do//递推循环 { maxx++; for (i = 1; i <= m; i++) if (maxx - x[i] >= 0) {//循环,建立递推关系式PIECES[i]=MAX(PIECES[I-X[j]]+1) if (pieces[maxx] == 0) pieces[maxx] = pieces[maxx-x[i]] + 1; if (pieces[maxx]>pieces[maxx-x[i]]+1) pieces[maxx] = pieces[maxx-x[i]]+1; } if ((pieces[maxx] == 0) || (pieces[maxx] > n)) { cout << maxx - 1; break; }} while (true); return 0; }