学步园

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1334

一开始直接贪心,0msWA……

其实这是个背包……太水了直接看代码吧

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=333;
int n,ans;
int w[maxn],sum,f[100010];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i],sum+=w[i];
	int m=sum/2; sort(w+1,w+1+n,greater<int>());
	for(int i=1;i<=n;i++)for(int j=sum;j>=w[i];j--)
	if((f[j-w[i]]<=m&&f[j-w[i]]+w[i]>m)||f[j-w[i]]+w[i]<=m)
	f[j]=max(f[j],f[j-w[i]]+w[i]);
	cout<<*max_element(f+1,f+1+sum)<<endl;
}