先按物品总价降序排序，背包容量限制在\(\dfrac m2+a[i]\)即可

排序可以用greater<int>()，省写cmp

#include
    
     #include
     
      #include
      
       using namespace std;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN = 10005;int n,m,ans;int a[MAXN],f[100005];int main(){    n=rd();    for(int i=1;i<=n;i++)m+=(a[i]=rd());    sort(a+1,a+1+n,greater
       
        ());    f[0]=1;    for(int i=1;i<=n;i++){        for(int j=m/2+a[i];j>=a[i];j--){            if(f[j-a[i]]){                f[j]=1;                ans=max(ans,j);            }        }    }    cout<
        
         <