题目描述
你有一架天平和$N$个砝码,这$N$个砝码重量依次是$W_{1},W_{2},···,W_{N}$。
请你计算一共可以称出多少种不同的正整数重量?
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数$N$。
第二行包含$N$个整数:$W_{1},W_{2},···,W_{N}$N。
输出格式
输出一个整数代表答案。
数据范围
对于$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。
算法一
dfs $O(3^{n})$ (TLE,过了一半数据)
C++代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, res;
int w[N];
bool st[N];
void dfs(int k, int sum)
{
if (k > n)
{
if (sum > 0 && !st[sum])
{
res ++ ;
st[sum] = true;
return;
}
}
else
{
dfs(k + 1, sum);
dfs(k + 1, sum + w[k]);
dfs(k + 1, sum - w[k]);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
dfs(0, 0);
cout << res << endl;
return 0;
}
算法二
dp $O(nm)$
C++代码
#include <iostream>
using namespace std;
const int N = 110, M = 200010, B = M / 2; //偏移量
int n, m;
int w[N];
bool f[N][M];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) scanf("%d", &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];
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 ++ ;
}
cout << res << endl;
return 0;
}