Description：

将 $n$ 个数字分组，每组的和不多于 $w$ ，问最少分几组。

$1\le n \le 18$

Solution：

一个显而易见的想法是把所有能分成组的放在一起跑背包，然而枚举子集 $3^n$ 会 $T$ ，于是考虑一个数一个数的转移，开一个辅助数组 $g$ 表示当前分组最后一个组还剩多少地方，如果下一个能放下则放，如果放不下就新开一个组。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,s;

#define MAXN 19

int w[MAXN];

int f[1 << MAXN],g[1 << MAXN];

int main()

{

	scanf("%d%d",&n,&s);

	for(int i = 1;i <= n;++i)scanf("%d",&w[i]);

	int tot = (1 << n) - 1;

	memset(f,0x3f,sizeof(f));

	memset(g,0,sizeof(g));

	f[0] = 0;

	for(int k = 0;k <= tot;++k)

	{

		for(int i = 1;i <= n;++i)

		{

			if(g[k] >= w[i])

			{

				if(f[k | (1 << (i - 1))] > f[k])

				{

					f[k | (1 << (i - 1))] = f[k];

					g[k | (1 << (i - 1))] = g[k] - w[i];

				}

				else if(f[k | (1 << (i - 1))] == f[k] && g[k] - w[i] > g[k | (1 << (i - 1))])

				{

					g[k | (1 << (i - 1))] = g[k] - w[i];

				}

			}

			else

			{

				if(f[k | (1 << (i - 1))] > f[k] + 1)

				{

					f[k | (1 << (i - 1))] = f[k] + 1;

					g[k | (1 << (i - 1))] = s - w[i];

				}

				else if(f[k | (1 << (i - 1))] == f[k] + 1 && s - w[i] > g[k | (1 << (i - 1))])

				{

					g[k | (1 << (i - 1))] = s - w[i];

				}

			}

		}

	}

	cout << f[tot] << endl;

	return 0;

}