DP(背包问题) - 砝码称重 - 第十二届蓝桥杯省赛第一场C++A/B组

题意：

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W 1 , W 2 , ⋅ ⋅ ⋅ , W N W_1,W_2,⋅⋅⋅,W_N W1​,W2​,⋅⋅⋅,WN​。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数： W 1 , W 2 , W 3 , ⋅ ⋅ ⋅ , W N 。 W_1,W_2,W_3,⋅⋅⋅,W_N。 W1​,W2​,W3​,⋅⋅⋅,WN​。

输出格式

输出一个整数代表答案。

数据范围

对于 50% 的评测用例，1 ≤ N ≤ 15。
对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 10⁵。

输入样例：

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。

分析：

有限制的选择问题，即背包问题。

每种物品有3种状态：不选、放左边（权值为正）、放右边（权值为负）。

状态转移方程：

f [ i ] [ j ] ： 考 虑 前 i 件 物 品 ， 是 否 能 够 称 出 的 质 量 为 j 的 物 品 。 记 ： f[i][j]：考虑前i件物品，是否能够称出的质量为j的物品。记： f[i][j]：考虑前i件物品，是否能够称出的质量为j的物品。记：

m = ∑ i = 1 n W i m=\sum_{i=1}^nW_i m=i=1∑n​Wi​

① 、 不 选 第 i 件 物 品 ， 则 f [ i ] [ j ] = f [ i − 1 ] [ j ] 。 ①、不选第i件物品，则f[i][j]=f[i-1][j]。 ①、不选第i件物品，则f[i][j]=f[i−1][j]。

② 、 第 i 件 物 品 放 左 边 ， 则 f [ i ] [ j ] = f [ i − 1 ] [ j − w [ i ] ] 。 ②、第i件物品放左边，则f[i][j]=f[i-1][j-w[i]]。 ②、第i件物品放左边，则f[i][j]=f[i−1][j−w[i]]。

③ 、 第 i 件 物 品 放 右 边 ， 则 f [ i ] [ j ] = f [ i − 1 ] [ j + w [ i ] ] 。 ③、第i件物品放右边，则f[i][j]=f[i-1][j+w[i]]。 ③、第i件物品放右边，则f[i][j]=f[i−1][j+w[i]]。

其 中 j ∈ [ − m , m ] ， 为 了 防 止 数 组 越 界 ， 我 们 给 j 加 上 偏 移 量 m ， 即 j ∈ [ 0 , 2 m ] 。 其中j∈[-m,m]，为了防止数组越界，我们给j加上偏移量m，即j∈[0,2m]。 其中j∈[−m,m]，为了防止数组越界，我们给j加上偏移量m，即j∈[0,2m]。

最 后 统 计 f [ n ] [ j ] （ j ∈ [ 1 , 2 m ] ） 中 ， 能 够 称 出 的 不 同 质 量 的 个 数 。 最后统计f[n][j]（j∈[1,2m]）中，能够称出的不同质量的个数。 最后统计f[n][j]（j∈[1,2m]）中，能够称出的不同质量的个数。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 110, M = 200010, B = M / 2;

int n, w[N], m;
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];
            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 = B+1; i <= m + B; i ++)
        if(f[n][i])
            res ++;
    
    cout<<res<<endl;
    
    return 0;
}