算法
放苹果
1
2
3
4
5
6
7
8
9
10
11
12
// u表示枚举到哪个盘子,sum表示剩余几个苹果，last表示枚举了多少个。
int dfs(int u, int sum, int last) {
    if(u == n) {
        if(!sum)
            return 1;
        return 0;
    }
    int res = 0;
    for(int i = last; i <= sum; i ++) 
        res += dfs(u + 1, sum - i, i);
    return res;
}
指数型枚举

用一个数组来表示三个状态，代替这个序列是升序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n;
int state[N];

void dfs(int u) {
    if(u > n) {
        for(int i = 1; i <= n; i ++) 
            if(state[i] == 1)
                cout << i << ' ';
        puts("");
        return ;
    }
    
    state[u] = 2;
    dfs(u + 1);
    state[u] = 0;
    
    state[u] = 1;
    dfs(u + 1);
    state[u] = 0;

}
费解的开关

用位运算枚举第一行的开关按法，每个灯泡只按一次，第一行按完之后，如果有熄灭的灯泡就需要第二行再按下，来确保第一行熄灭的灯泡变亮

需要注意的点：①要用一个备份数组，因为按下会改变原数组的值。②最后不需要考虑了，直接遍历看还有没有熄灭的灯泡。

组合型枚举

套用全排列模板，在此基础上更改即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int u, int last) {
    if(u > m) {
        for(int i = 1; i <= m; i ++)
            cout << path[i] << ' ';
        puts("");
        return;
    }

    for(int i = last + 1; i <= n; i ++) {
        if(!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u + 1, i);
            st[i] = false;
        }
    }
}
小猫爬山

深度优先搜索，void dfs(int u, int cnt)u表示枚举到哪知猫了，cnt表示现在有多少个缆车。有两种情况：①将猫加入已有的缆车当中。②将猫加入新的缆车。注意回溯复原。

优化：①如果枚举的最小还要大，那么直接返回。优先枚举较大的数。

图片详解

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
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 20;

int g[N], cab[N];
int n, w;
int ans;

void dfs(int u, int cnt) {
    if(cnt > ans)
        return;
    
    if(u == n) {
        ans = min(ans, cnt);
        return;
    }
    
    for(int i = 1; i <= cnt; i ++) {
        if(cab[i] + g[u] <= w) {
            cab[i] += g[u];
            dfs(u + 1, cnt);
            cab[i] -= g[u];
        }
    }
    
    cab[cnt + 1] = g[u];
    dfs(u + 1, cnt + 1);
    cab[cnt + 1] = 0;
    
}

int main() {
    cin >> n >> w;
    for(int i = 0; i < n; i ++)
        cin >> g[i];
    sort(g, g + n, greater<int>());
    
    ans = n;
    
    dfs(0, 0);
    
    cout << ans << endl;
    
    return 0;
}