蓝桥杯2021年第十二届省赛真题-砝码称重

解题思路:   众所周知   天平右边放砝码，左边放物品。

f[i][j]代表前i个砝码是否可以称出j的重量,f[i][j]=1表示存在f[i][j]=0表示不存在。
状态转移方程：当f[i-1][j]=1时,第i个砝码重量为a
f[i][j]=1,第i个砝码不使用
f[i][j+a]=1,第i个砝码和之前能称出的重量j相加
f[i][j-a]=1,两相减
f[i][a-j]=1,两相减
这四个状态代表了，当前i-1个砝码能称出j重量时可以和新加入的砝码称出的四个新状态，但这个重量可能会有负数的，所以默认加上100000当作一个偏移量，最后计算结果再减去即可。

其时当发现一个重量可以得负数，再和以后的状态做加减转化时，正数减去也能代表负数，
如 有砝码 2 1 3
前俩可以拼凑出的状态 1 2 3 -1，
3 + （-1）和 3 - 1 效果是一样的，所以负的重量状态抛弃掉最后结果也是不变的

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int sum;
int n;
int w[105];
int ans=0;
int f[105][100005];
int main()
{
    cin>>n;
    for (int i=1;i<=n; i++)
    {
        scanf("%d",&w[i]);
        sum+=w[i];
    }
    f[0][0]=1;
    for (int i =1; i<=n;i++)
        for (int j=0; j<=sum;j++)
            f[i][j]=f[i-1][j]||f[i-1][j+w[i]]||f[i-1][abs(j-w[i])];
                //只要有一个非空,f[i][j]就非空
    for (int i=1; i<=sum;i++)
        if(f[n][i])
ans++;
//不为零说明可以选出这个质量的砝码
    cout << ans;

    return 0;
}