https://blog.csdn.net/weixin_51176105/article/details/120300204 可谓之01背包变种 注意此处其实是在赋值false true
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N =2e5+20;
ll n,m,k;
struct cmp {
bool operator()(const int&a,const int&b) const {
return a>b;
}
};
int P = N/2;
bool dp[105][200010];
int w[105];
ll sum =0;
int main() {
cin >> n;
for(int i =1;i<=n;i++)
{
cin >>w[i];
sum+=w[i];
}
memset(dp,0,sizeof(dp));
dp[0][P]=1;
for(int i =1;i<=n;i++){
for(int j =-sum;j<=sum;j++){
dp[i][j+P]=dp[i-1][j+P];
if(j-w[i]>=-sum) dp[i][j+P]|=dp[i-1][j+P-w[i]];
if(j+w[i]<=sum) dp[i][j+P]|=dp[i-1][j+P+w[i]];
//if(j-w[i]>=-sum) dp[i][j+P]=max(dp[i][j+P],dp[i-1][j+P-w[i]]);
//if(j+w[i]<=sum) dp[i][j+P]=max(dp[i][j+P],dp[i-1][j+P+w[i]]);
}
}
int ans = 0;
for(int i =1;i<=sum;i++){
if(dp[n][i+P]) ans++;
}
cout <<ans;
return 0;
}
//3
//1 4 6