newcoder 清华 最小邮票数

发表于

清华复试上机 最小邮票数 题解

题目描述：

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

输入描述:

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

输出描述:

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

​ 本题是一个01背包的变形，将每张邮票的价值看作1，要求在背包容量必须装满的情况下，价值达到最小。可以用动态规划来解决。

​ 可以用一个二维数组dp[i][j]来表示在前i张里面填满空间j的最小邮票张数，则有dp[i][j] = min(dp[i -1][j] , dp[i - 1][j - ticket[i]] + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int main() {
    int M, N;
    int dp[101];
    int ticket[21];
    while(cin >> M >> N) {
        for(int i = 0; i < N; i++) 
            cin >> ticket[i];//用数组ticket来存储第i张邮票的价值
        for(int i = 0; i < 101; i++)
            dp[i] = N + 1;//面值为i时需要的邮票数量,将其统一初始化为当前的最大值N+1
        dp[0] = 0;
        dp[ticket[0]] = 1;
        for(int i = 1; i <= N; i++) {//i张邮票
            for(int j = M; j >= ticket[i]; j--) {
                    dp[j] = min(dp[j], dp[j - ticket[i]] + 1);
            }
        }
        if(dp[M] <= N)
            cout << dp[M] << endl;
        else
            cout << 0 <<endl;
    }
    return 0;
}