九度oj 题目1209：最小邮票数

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

样例输出：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #define MAX 22
 6 
 7 int ticket[MAX];
 8 int flag[MAX];
 9 int min;
10 
11 void dfs(int target, int end, int cnt) {
12     if(cnt > min) {
13         return;
14     }
15     if(target == 0) {
16         if(cnt < min) {
17             min = cnt;
18             return;
19         }
20     }
21     for(int i = end-1; i >= 0; i--) {
22         if(flag[i] == 0 && ticket[i] <= target) {
23             flag[i] = 1;
24             dfs(target - ticket[i], i,cnt + 1);
25             flag[i] = 0;
26         }
27     }
28 }
29 
30 int main()
31 {
32     
33     int n, m;
34     while(scanf("%d",&n) != EOF) {
35         
36         scanf("%d",&m);
37         for(int i = 0; i < m; i++) {
38             scanf("%d",&ticket[i]);
39         }
40         memset(flag,0,sizeof(flag));
41         min = m+1;
42         dfs(n,m,0);
43         if(min != m+1) {
44             printf("%d
",min);
45         }
46         else {
47             puts("0");
48         }
49         
50     }
51     return 0;
52 }

这道题考虑的是回溯法，并用类似天平的思想，从大到小依次加砝码。如果不行，全都移除，从下一个大的开始继续加。

这道题也能用动态规划求解，时间要稍长一些

写了一个简单的代码：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <cmath>
 6 #define MAX 22
 7 #define inf 1000002
 8 using namespace std;
 9 
10 int ticket[MAX];
11 int dp[MAX][102];
12 
13 
14 int main()
15 {
16     //freopen("input.txt","r",stdin);
17     int n, m;
18     while(scanf("%d",&n) != EOF) {
19         
20         scanf("%d",&m);
21         for(int i = 0; i < m; i++) {
22             scanf("%d",&ticket[i]);
23         }
24         
25         for(int r = 0; r <= n; r++) {
26             for(int i = 0; i < m; i++) {
27                 dp[i][r] = inf;
28             }
29         }
30         
31         for(int i = 0; i <=n; i++) {
32             dp[i][0] = 0;
33         }
34         dp[0][ticket[0]] = 1;
35         for(int r = 1; r <= n; r++) {
36             for(int i = 1; i < m; i++) {
37                 if(r >= ticket[i]) {
38                     dp[i][r] = min(dp[i-1][r],dp[i-1][r-ticket[i]] + 1);
39                 }
40                 else {
41                     dp[i][r] = dp[i-1][r];
42                 }
43             }
44         }
45 
46         if(dp[m-1][n] != inf) {
47             printf("%d
", dp[m-1][n]);
48         }
49         else {
50             puts("0");
51         }
52         
53     }
54     return 0;
55 }

主要的难点在于初始化和转移方程