165.小猫爬山

这类分组问题无非就是两种搜索顺序：

1.对于每个元素，枚举它可能分配到哪一个组

2.对于每个组，枚举它可能容纳哪些元素

这道题先把猫的体重从大到小排序，可以减小状态空间：

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;

const int N = 20, INF = 1e9;
int n, m, ans = INF;
int a[N], w[N];

void dfs(int Now, int Cars)
{
    if(Cars >= ans) return;
    if(Now == n + 1)
    {
        ans = Cars;
        return ;
    }
    for(int i = 1; i <= Cars; i++)
     if(w[i] + a[Now] <= m) 
      {
        w[i] += a[Now];
        dfs(Now + 1, Cars);
        w[i] -= a[Now];
      }
    w[Cars + 1] = a[Now];
    dfs(Now + 1, Cars + 1);
    w[Cars + 1] = 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
     cin >> a[i];
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    dfs(1,0);
    cout << ans << endl;
    return 0;
}

这里用的是方式1，他会不会存在像2一样的问题呢？即虽然避免了组内冗余，但是无法消除组间冗余：

例如，{1,2,3,4}最后的理想分组是{1,3}和{2,4}    

但是在枚举到{1，3}{2,4}之后，又枚举到了{2，4}{1,3}

幸运的是，枚举方式1不会出现组间冗余

因为我们在枚举1号猫的时候，还不存在任何一组，我们只能把他放到第一组来，它不可能会被放到第二组

又因为我们是按照猫的编号从小到大枚举的，所以第一个被处理的只可能是1号猫

因此它只可能出现在组1，不可能出现在组2

对于规模更大的情况，同理