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 Output2 13
1 71
4. 程序实现（Java语言）
1
2
/** *//**
3
* @(#)Ex5_1.java
4 *
5 *
6 * @author 叶云策（Intrl）
7 * @version 1.00 2009/5/22
8
*/
9
10import java.io.*;
11import java.util.*;
12public class Ex6_2
13
{
14 static int q=0;
15 public static void main(String[] args) throws Exception
16
{
17 Ex6_2 intrl=new Ex6_2();
18 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
19 System.out.println("请输入测试例个数:");
20 String str=br.readLine();
21 int mm=Integer.parseInt(str);
22 intrl.Test(mm);
23
}
24
25 public void Test(int mm)
26 {
27 int[][] result=new int[mm][2];
28 for(int i=0;i<mm;i++)
29 {
30 try
31 {
32 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
33 System.out.println("总测试例个数为"+mm+",现请输入第"+(i+1)+"个用例，数据由两行组成:");
34 String str1=br.readLine();
35 String[] str2=str1.split(" ");
36 int n=Integer.parseInt(str2[0]);
37 int m=Integer.parseInt(str2[1]);
38 String str3=br.readLine();
39 String[] str4=str3.split(" ");
40 int[] a=new int[n];
41 for(int j=0;j<n;j++)
42 {
43 a[j]=Integer.parseInt(str4[j]);
44 }
45 result[i][0]=getMin(a);
46 result[i][1]=YP(a,m);
47 }
48 catch(IOException e)
49 {
50 System.out.println(e);
51 }
52 }
53 System.out.println();
54 System.out.println("结果：");
55 for(int r=0;r<mm;r++)
56 {
57 System.out.println("["+result[r][0]+","+result[r][1]+"]");
58 }
59 }
60 /*核心算法*/
61 public int YP(int[] a,int m)
62 {
63 int min=getMin(a);
64 int max=min;
65 while(f(a,max,m))
66 {
67 //System.out.println(max+"--YP--");
68 max++;
69 }
70 //System.out.println("--------------------");
71 return max-1;
72 }
73 //判断result是否能否由不多于m个的数组a中的元素组成
74 public boolean f(int[] a,int result,int m)
75 {
76 //System.out.println(result+">>>>>"+q++);
77 if(m<=0)
78 {
79 return false;
80 }
81
82 for(int i=0;i<a.length;i++)
83 {
84 //System.out.println("-------"+q++);
85 if(result-a[i]==0)
86 {
87 //System.out.println(result+"--");
88 return true;
89 }
90
91 else if(result-a[i]>0)
92 {
93 if(f(a,result-a[i],m-1))
94 {
95 return true;
96 }
97 }
98 }
99 return false;
100 }
101
102 //该方法获取数组中的最小元素
103 public int getMin(int[] a)
104 {
105 int min=a[0];
106 for(int i=0;i<a.length;i++)
107 {
108 if(a[i]<min)
109 {
110 min=a[i];
111 }
112 }
113 return min;
114 }
115}
5. 运行结果截图
