Description：

有 $n$ 种面值的硬币，面值分别为 $b_1, b_2,\dots,b_n$ 。每种硬币有数量限制，想要凑出面值 $k$ 求最少要用多少个硬币。

$1\leqslant n\leqslant 200$

Solution：

裸的多重背包，但是卡空间，于是二进制拆分，记录一下每个拆开的物品属于哪个原来的物品，然后这样记录方案就不用记 $pre$ 了，只用记录 $used[i][j]$ 表示第 $i$ 个物品在第 $j$ 个容积是否被使用，这样只用 $bool$ 数组就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 210

int a[MAXN];

#define MAXO 2010

int b[MAXO],c[MAXO],tot = 0;

int bel[MAXO];

#define MAX 20010

int f[MAX];

bool used[MAXO][MAX];

int k;

int ans[MAXN];

int main()

{

	scanf("%d",&n);

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

	int w;

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

	{

		scanf("%d",&w);

		for(int k = 0;(1 << k) <= w;++k)

		{

			++tot;

			b[tot] = (1 << k) * a[i];w -= (1 << k);

			c[tot] = (1 << k);bel[tot] = i;

		}

		if(w != 0)

		{

			++tot;

			b[tot] = w * a[i];c[tot] = w;

			bel[tot] = i;

		}

	}

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

	f[0] = 0;

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

	{

		for(int j = MAX;j >= b[i];--j)

		{

			if(f[j - b[i]] + c[i] < f[j])

			{

				f[j] = f[j - b[i]] + c[i];

				used[i][j] = true;

			}

		}

	}

	scanf("%d",&k);

	cout << f[k] << endl;

	int cur = k;

	for(int i = tot;i >= 1;--i)

	{

		if(used[i][cur])

		{

			ans[bel[i]] += c[i];

			cur -= b[i];

		}

	}

	for(int i = 1;i <= n;++i)printf("%d ",ans[i]);

	puts("");

	return 0;

}