算法设计 邮票问题
算法设计 邮票问题
1. 问题描述
设有n种不同面值a1, a2,…, an的邮票,规定每封信最多贴m张邮票。对于给定的m,n,求出最大的邮资连续区间。例如,给定n=3,m=3,邮票面值分别为2, 3, 5,则最大的邮资连续区间为[2,13]。
2. 具体要求
Input
输入的第一行是一个正整数n,表示测试例个数。接下来几行是n个测试例的数据,每个测试例的数据由两行组成,其中第一行含两个正整数n和m (1<=n, m<=10),表示有n种邮票,每封信最多贴m张邮票;第二行含n个正整数,表示n种邮票的面值。同一行整数之间用一个空格隔开。
Output
对于每个测试例输出一行,含两个整数,依次为最大的邮资连续区间的下界和上界,当存在多个最大的邮资连续区间时,输出下界值最小的一个。同一行两个整数之间用一个空格隔开。
3. 测试数据
Sample Input
2
3 3
2 3 5
4 5
1 4 12 21
Sample Output
2 13
1 71
代码:
/// <summary>
/// 是否可以选出目标价值
/// </summary>
/// <param name="stamp">邮票面值</param>
/// <param name="n">邮票数组大小</param>
/// <param name="tar">目标价值</param>
/// <param name="m">最多可以选择的邮票张数</param>
/// <param name="find">是否找到目标价值的解</param>
/// <param name="count">当前已经选择的邮票张数</param>
/// <param name="cur">当前价值</param>
/// <param name="next">接下来要选择的邮票的价值</param>
void select(int* stamp, int n, int tar, int m, bool& find, int count, int cur, int next)
{if (count > m || find == true) // 张数超出或已经找到{return;}else{cur += next;if (cur == tar) // 找到目标价值{find = true;}for (int i = 0; i < n && !find; i++) // 按照顺序每次加入一张邮票{select(stamp, n, tar, m, find, count + 1, cur, stamp[i]);}}
}void test2()
{int n;cin >> n;while (n--){int n, m;cin >> n >> m;int* stamp = new int[n];for (int i = 0; i < n; i++){cin >> stamp[i];}int minstamp = *min(stamp, stamp + n - 1);int maxstamp = *max(stamp, stamp + n - 1);int start = minstamp;int maxstart = start;int end = minstamp;int maxend = end;int len = 0;int maxlen = len;bool find = false;for (int i = minstamp; i <= maxstamp * m; i++){select(stamp, n, i, m, find, 0, 0, 0);if (find) // 找到目标价值的邮票组合{end = i;len++;find = false;}else{if (len > maxlen) // 如果当前找到的区间更长则替换{maxlen = len;maxstart = start;maxend = end;}start = i + 1;end = i + 1;len = 0;}}cout << maxstart << " " << maxend << endl;delete[] stamp;}
}
截图:
算法设计 邮票问题
算法设计 邮票问题
1. 问题描述
设有n种不同面值a1, a2,…, an的邮票,规定每封信最多贴m张邮票。对于给定的m,n,求出最大的邮资连续区间。例如,给定n=3,m=3,邮票面值分别为2, 3, 5,则最大的邮资连续区间为[2,13]。
2. 具体要求
Input
输入的第一行是一个正整数n,表示测试例个数。接下来几行是n个测试例的数据,每个测试例的数据由两行组成,其中第一行含两个正整数n和m (1<=n, m<=10),表示有n种邮票,每封信最多贴m张邮票;第二行含n个正整数,表示n种邮票的面值。同一行整数之间用一个空格隔开。
Output
对于每个测试例输出一行,含两个整数,依次为最大的邮资连续区间的下界和上界,当存在多个最大的邮资连续区间时,输出下界值最小的一个。同一行两个整数之间用一个空格隔开。
3. 测试数据
Sample Input
2
3 3
2 3 5
4 5
1 4 12 21
Sample Output
2 13
1 71
代码:
/// <summary>
/// 是否可以选出目标价值
/// </summary>
/// <param name="stamp">邮票面值</param>
/// <param name="n">邮票数组大小</param>
/// <param name="tar">目标价值</param>
/// <param name="m">最多可以选择的邮票张数</param>
/// <param name="find">是否找到目标价值的解</param>
/// <param name="count">当前已经选择的邮票张数</param>
/// <param name="cur">当前价值</param>
/// <param name="next">接下来要选择的邮票的价值</param>
void select(int* stamp, int n, int tar, int m, bool& find, int count, int cur, int next)
{if (count > m || find == true) // 张数超出或已经找到{return;}else{cur += next;if (cur == tar) // 找到目标价值{find = true;}for (int i = 0; i < n && !find; i++) // 按照顺序每次加入一张邮票{select(stamp, n, tar, m, find, count + 1, cur, stamp[i]);}}
}void test2()
{int n;cin >> n;while (n--){int n, m;cin >> n >> m;int* stamp = new int[n];for (int i = 0; i < n; i++){cin >> stamp[i];}int minstamp = *min(stamp, stamp + n - 1);int maxstamp = *max(stamp, stamp + n - 1);int start = minstamp;int maxstart = start;int end = minstamp;int maxend = end;int len = 0;int maxlen = len;bool find = false;for (int i = minstamp; i <= maxstamp * m; i++){select(stamp, n, i, m, find, 0, 0, 0);if (find) // 找到目标价值的邮票组合{end = i;len++;find = false;}else{if (len > maxlen) // 如果当前找到的区间更长则替换{maxlen = len;maxstart = start;maxend = end;}start = i + 1;end = i + 1;len = 0;}}cout << maxstart << " " << maxend << endl;delete[] stamp;}
}
截图: