首页 > ACM题库 > 九度OJ > 九度-1209-最小邮票数[解题代码]
2013
12-13

九度-1209-最小邮票数[解题代码]

题目来源:2007年清华大学计算机研究生机试真题

题目描述:

    有若干张邮票,要求从中选取最少的邮票张数凑成一个给定的总值。
    如,有1分,3分,3分,3分,4分五张邮票,要求凑成10分,则使用3张邮票:3分、3分、4分即可。

输入:

    有多组数据,对于每组数据,首先是要求凑成的邮票总值M,M<100。然后是一个数N,N〈20,表示有N张邮票。接下来是N个正整数,分别表示这N张邮票的面值,且以升序排列。

输出:

      对于每组数据,能够凑成总值M的最少邮票张数。若无解,输出0。

样例输入:
10
5
1 3 3 3 4
样例输出:
3

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	static int sum;
	static int n;
	static int arr[];
	static int MAX = 99999;
	static int opt[][];
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextInt()){
			sum = s.nextInt();
			n = s.nextInt();
			arr = new int[n];
			opt = new int[n+1][sum+1];
			for(int i=0; i<n; i++)
				arr[i] = s.nextInt();
			Arrays.sort(arr);
			int r = f(n-1,sum);
			if(r >= MAX)
				System.out.println(0);
			else
				System.out.println(r);
		}
	}
	static int f(int i,int sum){
		if(sum <= 0)
			return MAX;
		if(opt[i][sum] > 0)
			return opt[i][sum];
		if(Arrays.binarySearch(arr, 0, i+1, sum) >= 0){
			opt[i][sum] = 1;
			return opt[i][sum];
		}
		else if(i > 0){
			return opt[i][sum]=Math.min(f(i-1,sum-arr[i])+1, f(i-1,sum));
		}
		if(i==0)
			return opt[i][sum]= (arr[0] == sum ? 1:MAX);
		return opt[i][sum];
	}

}
/**************************************************************
	Problem: 1209
	User: coder
	Language: Java
	Result: Accepted
	Time:2550 ms
	Memory:104608 kb
****************************************************************/


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。