By yusijia

Updated:

Contents
  1. 1. 题目：
    1. 1.1. 方法一：给面值排个序，深搜加剪枝
    2. 1.2. 方法二：动态规划
  • 白皮书训练

题目：

　　有n种硬币，面值分别为V1,V2…Vn，每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。 (1<=n<=100, 0<=S<=10000, 1<=Vi<=S)

方法一：给面值排个序，深搜加剪枝

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

const int N = 100;

int arr[N], flag, n;

void solve1(int sum, int counts)
{
    if(sum == 0){
        printf("min: %d\n", counts);
        flag = 1;
        return ;
    }
    if(!flag){
        for(int i = n - 1; i >= 0; i--){
            if(sum - arr[i] >= 0 && !flag){
                solve1(sum - arr[i], counts + 1);//转换到下一个状态
            }
        }
    }
}

void solve2(int sum, int counts)
{
    if(sum == 0){
        printf("max: %d\n", counts);
        flag = 1;
        return ;
    }
    if(flag == 0){
        for(int i = 0; i < n; i++){
            if(sum - arr[i] >= 0 && !flag){
                solve2(sum - arr[i], counts + 1);
            }
        }
    }
}

int main()
{
    int sum, counts;
    while(scanf("%d", &n) != EOF){
        for(int i = 0; i < n; i++){
            scanf("%d", &arr[i]);
        }
        sort(arr, arr + n);
        scanf("%d", &sum);
        counts = 0;
        flag = 0;
        solve1(sum, counts);
        counts = 0;
        flag = 0;
        solve2(sum, counts);
    }
    return 0;
}

方法二：动态规划

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 100;

int v[N];
int mins[N], maxs[N];//状态
int n, S;

//输出方案
void print_ans(int *d, int S)
{
    for(int i = 1; i <= n; i++){
        if(S >= v[i] && d[S] == d[S - v[i]] + 1){
            printf("%d ", v[i]);
            print_ans(d, S - v[i]);
            break;
        }
    }
}

int main()
{
    while(scanf("%d", &n) != EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d", &v[i]);
        }

        scanf("%d", &S);

        mins[0] = maxs[0] = 0;
        for(int i = 1; i <= S; i++){
            mins[i] = INF, maxs[i] = -INF;
        }
        for(int i = 1; i <= S; i++){
            for(int j = 1; j <= n; j++){
                if(i >= v[j]){
                    mins[i] = min(mins[i], mins[i - v[j]] + 1);//状态转移
                    maxs[i] = max(maxs[i], maxs[i - v[j]] + 1);
                }
            }
        }
        printf("min: %d\n", mins[S]);
        print_ans(mins, S);
        printf("\n");
        printf("max: %d\n", maxs[S]);
        print_ans(maxs, S);
        printf("\n");
    }
    return 0;
}
Contents
  1. 1. 题目：
    1. 1.1. 方法一：给面值排个序，深搜加剪枝
    2. 1.2. 方法二：动态规划