题解 | 砝码称重

题干解析

题设给予我们6种砝码，分别个，要求我们返回这些砝码能够组成的总重种数。

算法思路

本题可以进行一些转化，我们设定我们有一个承重为i的背包，设定状态值dp[i]表示装满这个背包的方案数。由此我们能够将整个问题转化为求dp数组，最后统计dp数组种的非零值的个数然后输出即为答案。

通过以上转化，我们将问题转化为一个背包DP问题。理论上本题数据量不大，能够直接转化为0/1背包进行求解，以下内容为对其进行二进制优化后的解法，通过将总数进行二进制拆分，优化时间复杂度。

实现代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<int> a(6);
    vector<int> m= {1, 2, 3, 5, 10, 20};
    int sum = 0;
    for (int i = 0; i < 6; ++i) {
        cin >> a[i];
        sum += a[i] * m[i];
    }
    // 二进制拆分优化
    vector<int> c;
    for (int i = 0; i < 6; ++i) {
        for (int j = 1; j <= a[i]; j <<= 1) {
            a[i] -= j;
            c.push_back(j * m[i]);
        }
        if (a[i]) {
            c.push_back(a[i] * m[i]);
        }
    }
    // DP
    vector<int> dp(sum + 1, 0);
    dp[0] = 1;
    for (auto i : c) {
        for (int j = sum; j >= i; --j) {
            dp[j] += dp[j - i];
        }
    }
    // 计数
    int N = 0;
    for (auto i : dp) {
        if (i) ++N;
    }
    cout << "Total=" << N - 1; // 重量为0不计入

    return 0;
}

复杂度分析

• 时间复杂度：
• 空间复杂度：