砝码称重

题目大意

你有一架天平和 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。

主要思路

通过读题得知该问题是有限制的选择问题，通俗的讲就是背包问题。
我们用f[i][j]表示在前i个物品里选，能不能凑成j这个重量，而往左边放砝码我们看作+w[i],往右边放砝码看作-w[i]，不放砝码为+0。
根据f[i][j]的不同划分方案的最后一个不同点划分为选第i个物品和不选第i个物品，选第i个物品划分为往左边放第i个物品和往右边放第i个物品。
不选第i个物品：f[i - 1][j]
往左边放第i个物品：f[i - 1]j - w[i]
往右边放第i个物品：f[i - 1]j + w[i]
由于这三种情况满足其中一种就能凑成f[i][j],所以将这三个值或运算起来即可
假设N个砝码总重量为m，需要注意的是由于我们能凑成重量区间为-m~+m，由于数组不能存在负数，于是我们在所有的j上加一个m的最大值100000当作偏移量来解决。

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 110, M = 200010, B = M / 2;//B为偏移量
int n, m, w[N];//m为当前所有砝码的重量和
int f[N][M];

int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
        m += w[i];
    }

    f[0][B] = true;//初始化，相当于f[0][0] = true
    for(int i = 1; i <= n; i++)
    {
        for(int j = -m; j <= m; j++)
        {
            f[i][j + B] = f[i - 1][j + B];//不选w[i]
            if(j - w[i] >= -m) f[i][j + B] |= f[i - 1][j - w[i] + B];//往左边放w[i]
            if(j + w[i] <= m) f[i][j + B] |= f[i - 1][j + w[i] + B];//往右边放w[i]
        }
    }

    int res = 0;
    for(int i = 1; i <= m; i++)//由于-m到-1能凑出来1到m也一定能凑出来，所以枚举1~m即可
    {
        if(f[n][i + B]) res++;
    }
    cout << res << endl;
    return 0;
}