传送门: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; }