【砝码称重】DP——很有意思的一道题

解题思路:

需要多思考，多思考

参考代码:

//砝码称重--dp 
#include <bits/stdc++.h>
using namespace std;
int n,w[110];
int dp[110][100005]; 
int ans = 0;
int main(){
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;++i){
		cin>>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] = max(dp[i-1][j],max(dp[i-1][j+w[i]],dp[i-1][abs(j-w[i])]));
		}
	}
	for(int i=1;i<=sum;++i){
		if(dp[n][i])
			ans++;
	}
	cout<<ans<<endl; 
	return 0;
}