HDU 2546食事カード（考える0-1バックパックが必要です。）

printf("%d
", m < 5 ? m : m - _01pack(n, m - 5) - w[n - 1]);

/*62ms,240KB*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx = 1005;

int w[mx], dp[mx];

int _01pack(int n, int maxw)
{
	memset(dp, 0, sizeof(dp));
	int i, j;
	for (i = 0; i < n - 1; ++i)
		for (j = maxw; j >= w[i]; --j)
			dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
	return dp[maxw];
}

int main()
{
	int n, m, i;
	while (scanf("%d", &n), n)
	{
		for (i = 0; i < n; ++i) scanf("%d", &w[i]);
		sort(w, w + n);
		scanf("%d", &m);
		printf("%d
", m < 5 ? m : m - _01pack(n, m - 5) - w[n - 1]);
	}
	return 0;
}