#include <bits/stdc++.h>
using namespace std;
#define N 200010
int dp[110][N]={0};//前i个砝码中可称j重量的状态
int n,w[N];
int main(){
scanf("%d",&n);
int sum = 0;
for(int i = 1 ; i <= n ; i ++){
scanf("%d",&w[i]);
sum += w[i];
}
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i ++){
for(int j = 0 ; j <= sum ; j ++){
dp[i][j] = dp[i-1][j] || dp[i-1][abs(j-w[i])] || dp[i-1][j+w[i]];
}
}
int count = 0;
for(int j = 1 ; j <= sum ; j ++){
if(dp[n][j]) count ++;
}
printf("%d",count);
return 0 ;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla