C++
$\color{gold}{— > 蓝桥杯辅导课题解}$
思路:
DP 背包问题
每个砝码只有三种情况:1.不选,2.选放在左边,3.选放在右边, 我们用 :0 + - 来表示这三种情况
闫氏DP分析法:
集合:只从前i个物品中选,且总重量为j的所有方案的集合
状态表示:
属性:是否非空(bool)
不选:f[i - 1][j]
状态计算: 选+w[i]:f[i - 1][j - w[i]]
选-w[i]:f[i - 1][j + w[i]]
$时间复杂度:O(nm)$
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 2e5 + 10, B = M / 2;
int n, m;
int w[N];
bool f[N][M];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> w[i], m += w[i];
f[0][B] = true;
for (int i = 1; i <= n; i ++)
for (int j = -m; j <= m; j ++) {
f[i][j + B] = f[i - 1][j + B]; // 加上一个偏移量让j为正数
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 i = 1; i <= m; i ++)
if (f[n][i + B])
res ++;
cout << res;
return 0;
}