C++ 代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int w[100010];
bool f[110][200010];//f[i][j]表示前i件物品能否组成重量为j的bool状态
int ans;//其中ans是答案
//我们可以使用DP,两层循环,第一层是遍历前i件物品，第二层是能不能取到j这么重
//对于每个砝码，要么取,要么不取,如果取，可以放在左边或者右边，就是加或者减

//if 不取，那么f【前i件砝码】【当前遍历到的重量】 = f【前i件砝码】【当前遍历到的重量】
//if 取,放在左边(+) f【前i件砝码】【当前遍历到的重量】 = f【前i-1件砝码】【当前遍历到的重量-第i个砝码的重量】 
//if 取,放在右边(-) f【前i件砝码】【当前遍历到的重量】 = f【前i-1件砝码】【当前遍历到的重量+第i个砝码的重量】
//因为给定一个重量,前i-1个砝码能取到,那么前i个砝码也能取到这个给定重量加上第i个砝码的重量或减去第i个砝码的重量
//因为两轮循环,所以在处理第前i个砝码的时候,第前i-1个砝码的状态已经全部处理好了

//还有一个坑,f数组存重量的地方要开大一倍,因为你要【当前遍历到的重量+第i个砝码的重量】
//如果j=100000,第i个砝码的重量为100000怎么办,所以要考虑这种情况,所以要开大一倍,sum*2;
int main()//因为N=100,所以用搜索肯定是不行的,用DP
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>w[i],sum+=w[i];

    f[0][0]=1;//先初始化，假如可以前1件物品可以组成总量为w[1]的总量，那么f[1][w[i]]=f[1-1][ w[i]-w[i] ]=f[0][0];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=sum;j++)
        {
            f[i][j]= f[i-1][j] || f[i-1][j+w[i]] || f[i-1][abs(j-w[i])];
            //只要满足一种情况存在,就保存记录下来,不管j是怎么搭配出来的
        }
    for(int i=1;i<=sum;i++)//从1到sum每个重量都遍历一遍
    {
        if(f[n][i])ans++;//这个总量能搭配出来,就++
    }
    cout<<ans;

    return 0;
}