真是佩服出这题的人。
1.首先基本思路：考虑对T与SUM-T分别进行背包，再min起来。为什么呢？难点在于SUM-T的是考虑有哪些数没有被选。
2.然后数据范围？？？瞬间吓尿。幸好有出题人指点，考虑分治。
3.然后？？细节比较烦。对于abs的和T=0的特判需要注意。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
long long n,t,num[105];
long long f[10000005],sum=0,kk=9999999999,rr=9999999999;
long long abs(long long a)
{
if (a<0) return -a;
return a;
}
long long dp(long long x)
{
memset(f,0,sizeof(f));
for (long long i=1;i<=n;i++)
for (long long j=x;j>=num[i];j--)
f[j]=max(f[j],f[j-num[i]]+num[i]);
return f[x];
}
void dfs(long long x,long long now)
{
if (x==n+1)
{
kk=min(kk,abs(now-t));
return;
}
else
{
dfs(x+1,now);
dfs(x+1,now+num[x]);
}
}
int main()
{
scanf("%lld%lld",&n,&t);
for (int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);
sum=sum+num[i];
rr=min(rr,num[i]);
}
if (t==0) printf("%lld
",rr);
else if (t<10000000)
{
long long minn=12345678;
minn=min(minn,abs(t-dp(t)));
minn=min(minn,abs(sum-t-dp(sum-t)));
printf("%lld
",minn);
}
else
{
dfs(1,0);
printf("%lld
",kk);
}
return 0;
}