相当于背包问题
对于每个砝码wi都有三种选择
0 不选
- 减去wi的重量
+ 加上wi的重量
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 110, M = 2e5 + 10, B = M / 2;
int n, m; //n为砝码数量, m为所有砝码加起来的总重量
int w[N]; //w数组用来存每个砝码的重量
bool f[N][M]; //Dp, 从前i个物品中选, 总重量为j的所有方案的集合
//集合属性: 十分存在这样的方案
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), m += w[i];
f[0][B] = true; // 0这个重量是可以做到的, 为了避免负数的情况, 所以加上偏移量B
for (int i = 1; i <= n; i ++ )
for (int j = -m; j <= m; j ++ ) //可以称重量的范围是-m ~ m
{
f[i][j + B] = f[i - 1][j + B]; //0 不选, 从f[i - 1][j + B]转移过来,且这种情况一定存在
if (j - w[i] >= -m) f[i][j + B] |= f[i - 1][j - w[i] + B]; //+ 加上当前砝码的重量
if (j + w[i] <= m) f[i][j + B] |= f[i - 1][j + w[i] + B]; //- 减去当前砝码的重量
}
int res = 0; //记录答案
for (int j = 1; j <= m; j ++ )
if (f[n][j + B]) res ++ ;
printf("%d\n", res);
return 0;
}