题面

迭代加深搜索模板题。

注意开始时要先对桶的容量从小到大排序。

达到搜索层数时使用完全背包\(\text{check}\)即可。

具体实现参考代码。

#include <bits/stdc++.h>

#define itn int

#define gI gi

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 103, maxm = 20003;

int d;//要搜索的层数

int mb, n, m, p, q[maxn], a[maxn], ans[maxn], sum;

bool f[maxm];

inline bool check()//完全背包check

{

	memset(f, false, sizeof(f));

	f[0] = true;

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

	{

		for (int j = 0; j + q[i] <= mb; j+=1)

			f[j + q[i]] |= f[j];

	}

	return f[mb];

}

bool dfs(int now, int hy)//迭代加深搜索

{

    //hy表示当前要枚举从hy到n的桶

    //这是枚举组合的常见写法

	if (now > d) return check();//达到了搜索的层数

	for (int i = hy; i <= p; i+=1)

	{

		q[now] = a[i];

		if (dfs(now + 1, hy + 1)) return true;//可行性搜索的省代码写法

	}

	return false;

}

int main()

{

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	mb = gi(), p = gi();

	for (int i = 1; i <= p; i+=1) a[i] = gi();

	sort(a + 1, a + 1 + p);//先排序

	for (d = 1; ; d+=1)

	{

		if (dfs(1, 1)) break;//有一组可行解

	}

	printf("%d", d);

	for (int i = 1; i <= d; i+=1) printf(" %d", q[i]);//当前的答案

	puts("");

	return 0;

}