题目链接

https://www.qduoj.com/problem/93

题目大意

判断是否能将一组数平均分成两份。

解题思路

一看到这个题感觉好像做过，但还是没做出来。
我成功的当成贪心去算了，wa不停。
正解是01背包恰好装满：
找个sum/2的背包，sum为数和。
每件物品的是每个数，每个数的值既是体积大小，又是自身价值。
最后只要看dp[sum/2]是否等于sum/2就行，这意味着sum/2大小的背包装下了价值为sum/2的东西。
对应到本题而言，意味着存在一组数的和正好为sum/2。

错误的贪心代码（我的）

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int a[N];
int sum1,sum2;
int n;
bool cmp(int x,int y){
    return x>y;
}
int main(){
    while(cin>>n){
        sum1=0;sum2=0;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++)
            sum1>sum2 ? sum2+=a[i] : sum1+=a[i];        
        cout<<(sum1==sum2 ? "YES" : "NO")<<endl;        
    }
}
//反例：5 4 3 2 2

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=205;
const int M=N*100;
int dp[M];
int n,sum;
int a[N];
int main(){
    while(cin>>n){        
        sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        if(sum&1){cout<<"NO"<<endl;}//判断为奇数
        else{
            memset(dp,0,sizeof dp);//勿忘
            sum/=2;
            for(int i=1;i<=n;i++)
                for(int j=sum;j>=a[i];j--)
                    dp[j]=max(dp[j-a[i]]+a[i],dp[j]);

            if(dp[sum]==sum)cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}

总结

感觉很简单一道题，而且好像还做过类似的，还是没做出来，我真的菜的抠jio。
还是要记住这种方法！！！
最后的最后，我还想再问上天一句：我什么时候才能成为大佬啊啊啊！！！