【洛谷题解】P1441 砝码称重

原题链接：https://www.luogu.com.cn/problem/P1441
难度：普及+/提高
涉及知识点：状态压缩DP

题意

有 $n$ 个砝码，第 $i$ 个砝码的重量为 $a_i$，在去掉 $m$ 个砝码后，问最多能称量出多少不同的重量 （不包括 0）

分析与解决

考虑状态压缩DP，将每一种摆放的状态用 $n$ 为二进制数表示，某一位上为 1 则有砝码，为 0 则没有砝码。如果某一种状态上的 1 的数量恰好为 $n-m$，则用 $bitset$ 存储重量。先初始化 $bitset$的第 0 位为 1，也就是重量 0 是可以被称量出来的。然后循环这个状态的每一位，如果第 $j$ 位为 1，就将 $bitset$ 与左移 $weight[j]$ 位后的 $bitset$ 做并集操作。循环完毕后更新答案。

• 为什么要这个并集操作？
  将 $bitset$ 的为 1 的第 $j$ 位左移 $weight[j]$ 位，之后 $bitset$ 的第 $j+w[j]$ 位变为了 1，表示重量 $j+w[j]$ 是可以被称量出来的，最后更新答案时， $bitset$ 里有多少个 1，就有多少种重量。

当然呢，对于这题也有用 $dfs$ 和 $dp$ 结合起来的做法，这里笔者认为过于繁琐就不加以赘述了，感兴趣的读者可以阅读下面这篇博文：
https://www.luogu.com.cn/blog/hsfzLZH1/solution-p1441

AC代码

//一道经典的棋盘式状压DP
#include 
#include 
#include 

using namespace std;

const int N = 25, M = 1 << N;

int n, m, ans = -0x3f3f3f3f;
int weight[N];

//统计x中1的数量
int count(int x)
{
    int res = 0;
    for (int i = 0; i < n; i++) res += x >> i & 1;
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> weight[i];

    for (int i = 0; i < 1 << n; i++)
    { //枚举状态
        if (count(i) == n - m)
        {
            bitset<M> b;
            b[0] = 1;
            for (int j = 0; j < n; j++)
            {
                if (i >> j & 1) b |= b << weight[j];
            }
            ans = max(ans, (int)b.count());
        }
    }
    cout << ans - 1 << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42