刚学状压不是很理解
为什么下面这份代码中把

f[0] = 0;

换成

f[0] = 1;

才是正确的呢？如果状态=0的话按说只需要0个电梯就可以啊。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int R18 = 74;
int n, W, f[(1 << 18) + R18], a[R18];
int rest[(1 << 18) + R18];
signed main()
{
	scanf("%d%d", &n, &W);
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i);
	memset(f, INF, sizeof(f));
	f[0] = 1; rest[0] = W;
	for (int i = 0;  i < (1 << n); ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if ((i >> (j - 1)) & 1) continue;
			else
			{
				if (rest[i] >= a[j]) 
				{
					if (f[i | (1 << (j - 1))] >= f[i])
					{
						f[i | (1 << (j - 1))] = f[i];
						rest[i | (1 << (j - 1))] = max(rest[i] - a[j], rest[i | (1 << (j - 1))]);
					}
				}
				else
				{
					if (f[i | (1 << (j - 1))] >= f[i] + 1)
					{
						f[i | (1 << (j - 1))] = f[i] + 1;
						rest[i | (1 << (j - 1))] = max(rest[i | (1 << (j - 1))], W - a[j]); 
					}
				}
			}
		}
	}
	printf("%d", f[(1 << n) - 1]);
	return 0;
}