小猫爬山

DFS一共五种剪枝策略：

1. 优化搜索顺序
2. 排除等效冗余
3. 可行性剪枝
4. 最优性剪枝
5. 记忆化

此题用到了1、3、4。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

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

int n,m,ans = INF;
int w[N],sum[N];

void dfs(int u,int k)
{
    if(k >= ans)    //第二次剪枝：如果当前车辆数大于我们已知的最小的车辆数的话，就pass掉这种方案
        return;

    if(u == n)
    {
        ans = k;
        return;
    }

    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,greater<int>());   //第一次剪枝：将小猫按重量从大到小排序

    dfs(0,0);

    cout << ans;

    return 0;
}