砝码称重（c++dp解法）

解题思路:动态规划dp解法

1. for循环i不断加入砝码

2. 当前状态=不加/右加/左加 ：dp[i+1][j]=dp[i][j] || dp[i][j+w[i]] || dp[i][abs(j-w[i])];
   

   
   

参考代码:

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    int size=0;
    cin>>n;
    
    vector<int> w(n);
    for(int i=0;i<n;i++){
        cin>>w[i];
	size+=w[i];
    }
    vector<vector<bool> > dp(n+1,vector<bool>(size+1,false));
    
    //设定初始状态，（j==w[i]时，dp[?][j-w[i]=0]=true）
    dp[0][0]=true;
    
    for(int i=0;i<n;i++){
        for(int j=size;j>=0;j--){
        
            //dp[i][j+w[i]]中j+w[i]可能数组过界需要判断
            //使用大数组，例如dp[102][100003] 就不用判断过界，但是大数组无法使用局部变量，记得使用全局变量
           
            if(j<size+1-w[i]){
            	dp[i+1][j]=dp[i][j] || dp[i][j+w[i]] || dp[i][abs(j-w[i])];
	    }else{
		dp[i+1][j]=dp[i][j] || dp[i][abs(j-w[i])];
	    }
        }
    }
    int res=0;
    for(int i=1;i<=size;i++){
        if(dp[n][i]){
            res++;
        }
    }
    cout<<res;
    return 0;
}