Home AcWing 278 数字组合
Post
Cancel

AcWing 278 数字组合

Link

题意: 给定 N 个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,求有多少种选择方案。

最直观的思路就是 DFS, 但是显然会超时. 按照这道题的数据, DFS 可以过 10/11 个测试点, 最后一个 TLE 了.

不过 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,cnt;
int a[110];
void DFS(int x,int left){
    if(x==0){
        cnt++;
        return;
    }else if(x<0) return;
    for(int i=left;i<=n;++i)
        DFS(x-a[i],i+1);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    DFS(m,1);
    printf("%d\n",cnt);
    return 0;
}

既然 DFS 不行, 那就只能用动态规划了. 典型的 01 背包问题.

dp[i][j] 表示前 i 个数的和为 j 的方案数. 初始状态 dp[0][0]=1 表示前 0 个数的和为 0 的方案数是 1.

从另一个角度解释, 假设有 a[1]=m, 那么只要在上一步 (一个数也不取) 的基础上取第一个数就可以构成一种方案, 并且只有这一种取法, 即 dp[1][m]=1=dp[0][a[1]-a[1]].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,a,dp[10010];
int main() {
    scanf("%d%d",&n,&m);
    dp[0]=1; //前0个数总和为0的方案数为1
    for(int i=1;i<=n;++i){
        scanf("%d",&a);
        for(int j=m;j>=a;--j)
            dp[j]+=dp[j-a];
    }
    printf("%d\n",dp[m]);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.