【算法】邮票问题

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

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. 运行结果截图

posted on 2009-05-22 23:52 intrl 阅读(1078) 评论(2)  编辑 收藏 引用 所属分类: 数据结构与算法

评论

# re: 【算法】邮票问题 2009-05-25 10:08 TS,MPEG2,dvbc专家

http://www.cnitblog.com/dvb-dvb/

感觉你也爱搞算法,能否帮我优化一下:  回复  更多评论   

# re: 【算法】邮票问题 2009-05-27 15:34 intrl

@TS,MPEG2,dvbc专家
我也只是初学者,呵呵!我去看看,若能懂的话,当然可以!
  回复  更多评论   

只有注册用户登录后才能发表评论。
<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

随笔分类(55)

随笔档案(34)

网址收藏

资源下载

随笔导航

搜索

最新评论

阅读排行榜

评论排行榜