跳转链接
https://www.acwing.com/problem/content/3420/ 来源：第十二届蓝桥杯省赛第一场C++A/B组
题目描述
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。 请你计算一共可以称出多少种不同的正整数重量？ 注意砝码可以放在天平两边。
输入格式 输入的第一行包含一个整数 N。 第二行包含 N 个整数：W1,W2,W3⋅⋅⋅,WN。 输出格式 输出一个整数代表答案。 数据范围 对于 50% 的评测用例，1≤N≤15。 对于所有评测用例，1≤N≤100，N 个砝码总重不超过 105。 输入样例 3 1 4 6 输出样例 10 样例解释 能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 − 1；
10 = 4 + 6；
11 = 1 + 4 + 6。题解思路
详细解析在代码中体现 TIPS: "|=" 运算 => 0 |= 1 = 1 0 |= 0 = 0 可以用来改变当前状态 “f[i][j + B] |= f[i - 1][j - w[i] + B]” 相当于 if(f[i - 1][j - w[i] == 0) f[i][j + B] = 0;else f[i][j + B] = 1;
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 200010, B = M / 2; //B代表偏移量
int n, m; //n为砝码数量， m为所有砝码加起来的总重量
int w[N]; //n为砝码数量， m为所有砝码加起来的总重量
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;
}
