\(Easy\)

题意：给定 \(n\) 个砝码，每个砝码的重量为 \(w[i]\)，问随意选择 \(k\) 个砝码（\(1\)<=\(k\)<=\(n\)），能得到的不同重量的个数

// 可以转化为背包问题求恰好装满方案数
// 只不过，这个方案数我们只考虑0/1
// f[i]就表示装满体积i的方案数
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int M = 1010;

int w[] = {1, 2, 3, 5, 10, 20};
bool f[M];

int main()
{
    f[0] = 1;
    for(int i = 0; i < 6; i ++ )
    {
        int cnt;    cin >> cnt;
        while(cnt -- )
        {
            for(int j = M - 1; j >= w[i]; j -- )
                f[j] |= f[j - w[i]];
        }
    }
    
    
    int res = 0;
    for(int i = 0; i < M; i ++ )
        res += f[i];
    // 不包括重量为0的情况
    cout << "Total=" << res - 1 << endl;
    return 0;
}

\(Medium\)

给定 \(n\) 个砝码，问将 \(x\) 个放在砝码左侧，\(y\) 个放在砝码右侧，可以称出的重量有多少种（\(1\)<=\(x+y\)<=\(n\)）

思路一

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

using namespace std;

const int N = 110, M = 1e5 + 10;

int n, m, w[N];
bool f[2][M];   // 滚动数组优化
int res;

/*
f[i][j]:从前i个物品中选，称出重量为j的方案数(j=0/1)
我们规定：j = abs(left-right)
当前物品不选: f[i][j] |= f[i - 1][j]
当前物品选：
    f[i][j] |= f[i - 1][j - w]：放在左侧
    f[i][j] |= f[i - 1][j + w]：放在右侧
    当放在左侧且j-w<0时，例如j=1,w=2，再不妨设此时左侧为2,右侧为1，j=2-1=1
    [2] [1]
    -------
       |
    -------
    我们希望此时在左侧放一个重量w=2的砝码之后left-right=j=1，显然不可能啊！
    因为显然2+2-1=3，但其实，我们换一种角度想，如果left-right=1
    那么我们交换一下左右侧，变为：
    [1] [2]
    -------
       |
    -------
    此时left-right=-1不久存在了么
    因此说，当j-w<0时，由于数组下标不合法，我们可以将j-w改为abs(j-w)，它们是等价的
*/

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )   cin >> w[i], m += w[i];
    
    f[0 & 1][0] = 1;
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
        {
            f[i & 1][j] |= f[(i - 1) & 1][j];
            f[i & 1][j] |= f[(i - 1) & 1][abs(j - w[i])];
            if(j + w[i] <= m)   f[i & 1][j] |= f[(i - 1) & 1][j + w[i]];
        }
    for(int i = 1; i <= m; i ++ )   res += f[n & 1][i];
    cout << res << endl;
    return 0;
}

思路二

更直观的思路，为了处理负数的问题，添加一个偏移量即可！

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

using namespace std;

const int N = 110, M = 2e5 + 10, F = 1e5;

int n, m, w[N];
bool f[2][M];   // 滚动数组优化
int res;

/*
f[i][j]:从前i个物品中选，称出重量为j的方案数(j=0/1)
j=left-right
但是注意这样设置j的话，有 -m <= j <= m
因为体积为循环的时候是从 -m 到 m 而不是 0 到 m
*/

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )   cin >> w[i], m += w[i];
    
    f[0 & 1][0 + F] = 1;
    for(int i = 1; i <= n; i ++ )
        for(int j = -m; j <= m; j ++ ) // j=-m
        {
            f[i & 1][j + F] |= f[(i - 1) & 1][j + F];
            f[i & 1][j + F] |= f[(i - 1) & 1][j - w[i] + F];
            if(j + w[i] <= m)   f[i & 1][j + F] |= f[(i - 1) & 1][j + w[i] + F];
        }
    for(int i = 1; i <= m; i ++ )   res += f[n & 1][i + F];
    cout << res << endl;
    return 0;
}

\(Hard\)