P1441 砝码称重

题目描述

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

请注意，砝码只能放在其中一边。

输入格式

第 $1$ 行为有两个整数 $n$ 和 $m$，用空格分隔。

第 $2$ 行有 $n$ 个正整数 $a_1,a_2,a_3,\dots ,a_n$，表示每个砝码的重量。

输出格式

仅包括 $1$ 个整数，为最多能称量出的重量数量。

输入输出样例 #1

输入 #1

3 1
1 2 2

输出 #1

3

说明/提示

【样例说明】

在去掉一个重量为 $2$ 的砝码后，能称量出 $1,2,3$ 共 $3$ 种重量。

【数据规模】

对于 $20\%$ 的数据，$m=0$。

对于 $50\%$ 的数据，$m\le 1$。

对于 $50\%$ 的数据，$n\le 10$。

对于 $100\%$ 的数据，$n\le 20$， $m\le 4$，$m<n$，$a_i\le 100$。

solution

思路：因为砝码的数量和重量都比较小，总重量 <= 2000, 可以用s[i] = 0|1，来表示重量 i 是否可以称出来

• 但是2000位大大超过了基本数据的表示范围，考虑使用 bitset 来进行状态合并，因为可以方便的进行位运算，适合合并一个新砝码

• 1 定义公式

     i : 使用砝码的一种状态
     s[k]: 重量k是否可称出来

• 2 状态转移

      s = s | s << a[j]
      a[j] 为第 j 块砝码的重量, s << a[j] 将之前所有可以称出来的质量统一加上 a[j] 都可以称出来，然后与 s 求并集
      表示新加砝码 j 可以称出来的重量

• 3 结果

     s.count()
     s 为恰好使用 n - m 块砝码时可称出来的集合

• 4 初始状态

      s[0] = 1
      这样是为了合并时，算上单独使用新加的砝码

• 5 复杂度分析：

*      时间复杂度：
*          遍历砝码状态: 2^n <= 2^20
*          其中满足正好有 n - m 个砝码有 C(n, n - m) <= C(20, 4) = 4854
*          每一种状态要遍历 n 个砝码，并进行合并操作，大概是 2000 / 64 = 31.25
*          所以是 2^20 + 4854 * 20 * 31.25
*      空间复杂度：
*          2000 / 64

代码

#include <vector>
#include "iostream"
#include "algorithm"
#include "unordered_map"
#include "cstring"
#include "bit"
#include "bitset"

using namespace std;

/*
 * P1441 砝码称重
 * 题目大意：
 * 现有 n 个砝码，重量分别为 a[i]，在去掉 m 个砝码后，问最多能称量出多少不同的重量（不包括 0）。请注意，砝码只能放在其中一边。
 *
 * 数据范围：(n≤20, m≤4，m<n，a[i]≤100)
 *
 * 思路：因为砝码的数量和重量都比较小，总重量 <= 2000, 可以用s[i] = 0|1，来表示重量 i 是否可以称出来
 * 但是2000位大大超过了基本数据的表示范围，考虑使用 bitset 来进行状态合并，因为可以方便的进行位运算，适合合并一个新砝码
 *
 * 1 定义公式
 *      i : 使用砝码的一种状态
 *      s[k]: 重量k是否可称出来
 * 2 状态转移
 *      s = s | s << a[j]
 *      a[j] 为第 j 块砝码的重量, s << a[j] 将之前所有可以称出来的质量统一加上 a[j] 都可以称出来，然后与 s 求并集
 *      表示新加砝码 j 可以称出来的重量
 * 3 结果
 *      s.count()
 *      s 为恰好使用 n - m 块砝码时可称出来的集合
 * 4 初始状态
 *      s[0] = 1
 *      这样是为了合并时，算上单独使用新加的砝码
 *
 * 5 复杂度分析：
 *      时间复杂度：
 *          遍历砝码状态: 2^n <= 2^20
 *          其中满足正好有 n - m 个砝码有 C(n, n - m) <= C(20, 4) = 4854
 *          每一种状态要遍历 n 个砝码，并进行合并操作，大概是 2000 / 64 = 31.25
 *          所以是 2^20 + 4854 * 20 * 31.25
 *      空间复杂度：
 *          2000 / 64
 */

typedef long long ll;
const int N = 1e5 + 5, M = 1e8;

int n, m, a[25], ans;

int main() {

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

    for (unsigned i = 0; i < (1 << n); i++) {
        if (popcount(i) + m != n) continue; // 只考虑 n - m 块砝码
        bitset<2005> s; // s[i] = 0 ｜ 1  质量 i 可以｜不可以被称出来
        s.set(0); // 方便状态转移
        for (int j = 0; j < n; j++)
            if ((i >> j) & 1) // i 状态下用到了第 j 个砝码
                s |= s << a[j];
        ans = max(ans, int(s.count()));
    }

    cout << ans - 1 << endl;
    return 0;
}

结果