Fork me on GitHub

1068 Find More Coins (30分)

发表于 | 分类于 | 次阅读
字数统计: 850 | 阅读时长 ≈ 4

题目大意

有几个数字，问是否有其中几个数加起来等于给定的数，如果有多个结果，输出最小的一组。

https://pintia.cn/problem-sets/994805342720868352/problems/994805402305150976

解法一：dfs+特判

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
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

vector<int> v;
int n , m;
int sum = 0;
vector<int> money;
int book = 0;
void dfs(int u , int i){
    money.push_back(u);

    sum += u;
    //cout<<u<<' '<<sum<<endl;
    if(book){
        return;
    }
    if(sum == m){
        book = 1;
        for(int j = 0 ; j<money.size() ; ++j){
            if(!j){
                printf("%d" , money[j]);
            }
            else printf(" %d" , money[j]);
        }
        cout<<endl;
        return ;
    }
    else if(sum > m){
        money.pop_back();
        sum -= u;
        return ;
    }
    for(int j = i+1 ; j<n ; ++j){
        dfs(v[j] , j);
        if((sum + v[j+1]) > m) break;
    }
    money.pop_back();
    sum -= u;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d%d" , &n , &m);
    int ssum = 0;
    for(int i = 0 ; i<n ; ++i){
        int a;
        scanf("%d" , &a);
        if(a <= m){
            v.push_back(a);
            ssum += a;
        }
    }
    if(!v.size() || ssum < m){
        cout<<"No Solution";
        return 0;
    }
    sort(v.begin() , v.end());
    for(int i = 0 ; i<n ; ++i){
        sum = 0;
        book = 0;
        dfs(v[i] , i);
        money.clear();
        if(book){
            return 0;
        }
    }
    cout<<"No Solution";
}

如果不加特判，那么最后一点会超时，29分，这显然不是很好的解法

解法二：0-1背包

首先需要把序列从大到小排列，然后在dp，为什么呢？

看一组样例：5 9 8 7 2 3 4 1，容量为9

我们可以这样想，我们可以一个一个数地放入“背包”，如果符合条件dp[j] <= dp[j-weight[i]]+value[i]，那么我们就把i标记（flag[i][j] = 1），最终通过while遍历最小的数。当该放每组结果的最小的数时，由于我们是从大到小排列的，所以前面比它大的数已经把其他背包更新好了，比如1 3 5，由于3和5已经把背包8更新成8，所以1就被背包9标记了，所以其实我们最终是把每组结果在各个背包的第一个数（即小的数）标记，即大数把背包更新，最小的数在此铺垫上就被标记了，而题目要求我们输出最小的结果，所以这就是序列必须从大到小排列的原因。

启发：0-1背包由于我们是一个数一个数地放，所以当放第i个数时，前面i-1个数已经把背包更新好了，这就是铺垫，第i个数在此铺垫上更新背包。

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
#include <iostream>
#include <vector>
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
int dp[10010], w[10010];
bool flag[10010][110];
int cmp1(int a, int b){return a > b;}



int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    fill(flag[0] , flag[0] + 10010*110 , false);
    int n , m;
    cin>>n>>m;
    for(int i = 1 ; i<=n ; ++i){
        cin>>w[i];
    }
    sort(w+1 , w+n+1 , cmp1);
    for(int i = 1 ; i<=n ; ++i){
        for(int j = m ; j>=w[i] ; --j){
            if(dp[j] <= dp[j - w[i]] + w[i]){
                flag[i][j] = 1;
                dp[j] = dp[j - w[i]] + w[i];
            }
        }
    }
    if(dp[m] < m){
        cout<<"No Solution";
        return 0;
    }
    else {
        vector<int> v;
        int index = n;
        while(m){
            if(flag[index][m]){
                v.push_back(w[index]);
                m -= w[index];
            }
            index--;
        }
        for(int i = 0 ; i<v.size() ; ++i){
            if(i > 0){
                cout<<' ';
            }
            cout<<v[i];
        }
    }
}