题解 | #L2-1 特殊的沉重球#

dfs的一般优化(5种）

1优化搜索顺序

——大部分情况下，我们应该优先搜索分支较少的节点。在本题中，我们可以先从大到小排序。因为我们先选择大的，后面的选择就会减少，分支也会减少。相反，如果先搜索小的，后面的选择多，搜索的分支会变多。

2排除等效冗余

——本题我们搜索时是枚举每一个宝可梦应该放到哪个球里，已经没有重复搜索了。但如果枚举每一个球应该放哪些宝可梦则会增加搜索次数。

3可行性剪枝

——加上枚举到的宝可梦超过m时，则直接剪枝。

4最优化剪枝

——当k>=ans时,说明此时的方案继续搜素下去也不能再优化答案了，直接return。

5优化搜索顺序

——本题没有用到。

#include <bits/stdc++.h>
using namespace std;

int n, m;
int w[30];
int sum[30];
int ans = 20;//最多只有20组

int cmp(int a, int b)
{
    return a > b;
}

void dfs(int u, int k)
{
    //最优性剪枝
    if (k >= ans)
        return;
    if (u == n)
        ans = k;
    for (int i = 0; i < k; i++)
        if (sum[i] + w[u] <= m)//可行性剪枝
        {
            sum[i] += w[u];
            dfs(u + 1, k);
            sum[i] -= w[u];//恢复现场
        }
    //新加一个沉重球
    sum[k] = w[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;//恢复现场
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> w[i];

    //优化搜索顺序
    sort(w, w + n, cmp);

    dfs(0, 0);

    cout << ans << '\n';
}