题目链接：https://blog.csdn.net/Darost/article/details/52344013

老师已给代码，但转换式看不懂 完整代码：

int n,a,sum=0;
int num[105];
int dp[105][20005];
int main(){
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>num[i];
        sum+=num[i];
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=sum;j++){
            if(dp[i-1][j]>=0)
                dp[i][j]=dp[i-1][j];
            if(num[i] > j && dp[i - 1][num[i] - j] > -1)
				dp[i][j]=max(dp[i][j], dp[i-1][num[i]-j] + j);
            if(j+num[i] <= sum && dp[i - 1][j + num[i]] > -1)
				dp[i][j]=max(dp[i][j], dp[i - 1][j + num[i]]);
            if(j>=num[i] && dp[i - 1][j-num[i]] > -1)
				dp[i][j]=max(dp[i][j], dp[i - 1][j - num[i]] + num[i]);
        }
    if(dp[n][0]>0)cout<<dp[n][0];
    else cout<<"Impossible";
    return 0;
}

转换式：

for(int j=0;j<=sum;j++){
            if(dp[i-1][j]>=0)
                dp[i][j]=dp[i-1][j];
            if(num[i] > j && dp[i - 1][num[i] - j] > -1)
				dp[i][j]=max(dp[i][j], dp[i-1][num[i]-j] + j);
            if(j+num[i] <= sum && dp[i - 1][j + num[i]] > -1)
				dp[i][j]=max(dp[i][j], dp[i - 1][j + num[i]]);
            if(j>=num[i] && dp[i - 1][j-num[i]] > -1)
				dp[i][j]=max(dp[i][j], dp[i - 1][j - num[i]] + num[i]);
        }