题目链接：

 

01背包一眼题，没什么好解释……

背包容量是m-5，留下一个最贵不要在01背包里算，最后买。

没错我需要<algorithm>

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n, m, p[1005];int opt[1005];int nextInt() {	char c; while ((c = getchar()) < '0' || c > '9'); int r = c - '0';	while ((c = getchar()) >= '0' && c <= '9') (r *= 10) += c - '0';	return r;}int main() {	while (n = nextInt()) {		memset(opt, 0, sizeof opt);		for (int i = 1; i <= n; ++i)			p[i] = nextInt();		sort(p + 1, p + n + 1);		m = nextInt();		for (int i = 1; i < n; ++i)			for (int j = m - 5; j >= p[i]; --j)				if (opt[j - p[i]] + p[i] > opt[j])					opt[j] = opt[j - p[i]] + p[i];		if (m < 5) printf("%d\n", m);		else printf("%d\n", m - opt[m - 5] - p[n]);	}	return 0;}