Jobdu 1209最小邮票数 - KingEasternSun的专栏 - 博客频道 - CSDN.NET

九度笔记之 1209最小邮票数 - KingEasternSun的专栏 - 博客频道 - CSDN.NET

    有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。
    如，有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

void minNum(int m,int n){
    int *dp = new int[m+1];
    dp[0] = 0;
    for(int i = 1;i<=m;i++)
        dp[i] = INF;
    int *num = new int[n];
    for(int i = 0;i<n;i++)
        std::cin>>num[i];
    for(int i = 0;i<n;i++){
        for(int j = m;j>=num[i];j--){ //must from m to num[i]
            dp[j] = std::min(dp[j],dp[j-num[i]]+1);
        }
    }
    if(dp[m]<INF)
        std::cout<<dp[m]<<std::endl;
    else
        std::cout<<0<<std::endl;
}
void minNumnew(int m,int n){
    int *dp = new int[m+1];
    dp[0] = 0;
    for(int i = 1;i<=m;i++)
        dp[i] = INF;
 
    int num;
    for(int i = 0;i<n;i++){
        std::cin>>num;
        for(int j = m;j>=num;j--){ //must from m to num[i]
            dp[j] = std::min(dp[j],dp[j-num]+1);
        }
    }
    if(dp[m]<INF)
        std::cout<<dp[m]<<std::endl;
    else
        std::cout<<0<<std::endl;
}

http://www.acmerblog.com/jiudu-1209-2365.html

10	public static void main(String[] args) {

11	Scanner s = new Scanner(new BufferedInputStream(System.in));

12	while(s.hasNextInt()){

13	sum = s.nextInt();

14	n = s.nextInt();

15	arr = new int[n];

16	opt = new int[n+1][sum+1];

17	for(int i=0; i<n; i++)

18	arr[i] = s.nextInt();

19	Arrays.sort(arr);

20	int r = f(n-1,sum);

21	if(r >= MAX)

22	System.out.println(0);

23

else

24	System.out.println(r);

25

}

26

}

27	static int f(int i,int sum){

28	if(sum <= 0)

29	return MAX;

30	if(opt[i][sum] > 0)

31	return opt[i][sum];

32	if(Arrays.binarySearch(arr, 0, i+1, sum) >= 0){

33	opt[i][sum] = 1;

34	return opt[i][sum];

35

}

36	else if(i > 0){

37	return opt[i][sum]=Math.min(f(i-1,sum-arr[i])+1, f(i-1,sum));

38

}

39

if(i==0)

40	return opt[i][sum]= (arr[0] == sum ? 1:MAX);

41	return opt[i][sum];

42

}

Read full article from 九度笔记之 1209最小邮票数 - KingEasternSun的专栏 - 博客频道 - CSDN.NET