题解 | #称砝码#

使用动态规划的原理，算出砝码的总重量，根据重量建立相应长度的两个数组向量，对于每一个砝码，从重量0开始遍历，如果当前的重量减去此砝码的重量对应的重量存在，则当前重量标记为存在，否则复制之前的数组值，遍历完砝码后，对应的数组中1的数量就是重量组合的数量。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int weight[n];
    int num[n];
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> num[i];
        sum += num[i] * weight[i];
    }
    vector<vector<int>> dp(2, vector<int>(sum + 1, 0));
    dp[0][0] = 1;
    dp[1][0] = 1;
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= num[i]; j++) {
            for (int k = 0; k < weight[i]; k++) {
                dp[b][k] = dp[a][k];
            }
            for (int k = weight[i]; k <= sum; k++) {
                dp[b][k] = dp[a][k - weight[i]] == 1 ? 1 : dp[a][k];
            }
            int temp = a;
            a = b;
            b = temp;
        }
    }
    int ans = 0;
    int temp = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j <= sum; j++) {
            if (dp[i][j] == 1) {
                temp++;
            }
        }
        ans = max(ans, temp);
        temp = 0;
    }
    cout << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")