我的思路是分为三部分把所有的负数放在前面，0在中间，正数在后面。

所以先$nV$跑一下2000以内的背包，并用链表记录每个背包容积下需要使用的正数。有个细节是对于每个背包容积，都尽量保证最大的正数不被使用，因此背包前要对正数序列排个序。

最后枚举负数，对于每个负数，计算距离它绝对值最近的背包，然后加上那个背包所对应的未被使用的最大正数，求和一下更新答案。

#include <bits/stdc++.h>
const int N = 2005;
using namespace std;
int po[N], neg[N], n, tmp, cnt1=0, cnt2=0;
int anspo=0, minneg = N;
int vis[N], use[N], fa[N], a[N];
int main()
{
	cin>>n;
	for(int i=1; i<=n; ++i) 
	{
		scanf("%d", &tmp);
		if(tmp>0) po[++cnt1] = tmp, anspo+=tmp;
		if(tmp<0) neg[++cnt2] = -tmp, minneg=min(minneg, -tmp);
	}
	sort(po+1, po+cnt1+1);
	vis[0]=1;
	for(int i=1; i<=cnt1; ++i)
		for(int j=2000; j>=po[i]; --j)
			if(vis[j-po[i]]==1 && vis[j]==0) vis[j] = 1, use[j]=i,fa[j]=j-po[i];
	int ma = -2005;
	for(int i=1; i<=cnt2; ++i)
	{
		for(int j=neg[i]; j>=0; --j)
			if(vis[j]==1)
			{
				tmp = j-neg[i];
				memset(a,0,sizeof(a));
				int tt = j;
				while(j) 
					a[use[j]]=1, j=fa[j];
				
				for(int k=cnt1; k>=1; --k) 
					if(a[k]==0)
					{
						tmp += po[k];
						break;
					}
				ma = max(tmp, ma);
				break;
			}
	}
	if(cnt2 == 0)cout<<po[cnt1];
	else cout<<ma;
	return 0;
}