description：

N个政党要组成一个联合内阁，每个党都有自己的席位数.

现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好.

对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.

solution：

由于删除任意一个都要保证小于等于一半，所以只要保 证删除最小的那个后小于等于一半即可。

我们可以将所有党按照席位数从大到小排序，之后维护 一个 01 01 01背包。

fj表示通过前i大的党组成席位总数为j的内阁所占的席位

f j = m a x ( f j , ( f j − a i ) + a i ) f_j=max(f_j , (f_j−a_i)+a_i) fj​=max(fj​,(fj​−ai​)+ai​)

之后枚举满足 f [ j ] − a i ≤ s u m 2 2 f[j] −ai ≤ \frac{sum2}{2} f[j]−ai≤2sum2​ 并且 f [ j ] > s u m 2 2 f[j] > \frac{sum2}{2} f[j]>2sum2​ 的所有 f [ j ] f[j] f[j]，取最大值

时间复杂度 O ( n ∗ ∑ ︀ a i ) O(n*∑︀a_i) O(n∗∑︀ai​)，空间复杂度 O ( ∑ ︀ a i ) O(∑︀a_i) O(∑︀ai​)。

code:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[305];
int f[100005];
int main()
{
	int n,sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		//f[a[i]]=1;
		sum+=a[i];
	}
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=n;i>=1;i--)
	{
		for(int j=sum;j>=a[i];j--)
		{
			f[j]=max(f[j],f[j-a[i]]+a[i]);
			if(j-a[i]<=sum/2&&f[j]>sum/2)
			{
				ans=max(ans,f[j]);
			}
		} 
	} 
	printf("%d\n",ans);
	return 0;
}