题解 | 称砝码

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

int main() {
    int n;
    cin >> n;
    
    vector<int> weights(n);  // 每种砝码的重量
    vector<int> counts(n);   // 每种砝码的数量
    
    // 读取砝码重量
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    
    // 读取砝码数量
    for (int i = 0; i < n; i++) {
        cin >> counts[i];
    }
    
    // 计算可能的最大重量
    int max_weight = 0;
    for (int i = 0; i < n; i++) {
        max_weight += weights[i] * counts[i];
    }
    
    // 创建二维dp数组，dp[i][j]表示使用前i种砝码能否称出重量j
    vector<vector<bool>> dp(n + 1, vector<bool>(max_weight + 1, false));
    
    // 初始状态：不使用任何砝码可以称出重量0
    dp[0][0] = true;
    
    // 动态规划过程
    for (int i = 1; i <= n; i++) {
        // 获取当前砝码的重量和数量
        int weight = weights[i - 1];
        int count = counts[i - 1];
        
        // 对于每个可能的重量j
        for (int j = 0; j <= max_weight; j++) {
            // 首先，如果不使用当前砝码，则沿用前i-1种砝码的结果
            dp[i][j] = dp[i - 1][j];
            
            // 尝试使用不同数量的当前砝码
            for (int k = 1; k <= count; k++) {
                // 如果当前重量减去k个当前砝码后的重量能被称出，那么当前重量也能被称出
                if (j >= k * weight && dp[i - 1][j - k * weight]) {
                    dp[i][j] = true;
                    break;
                }
            }
        }
    }
    
    // 计算可以称出的不同重量数量
    int count = 0;
    for (int j = 0; j <= max_weight; j++) {
        if (dp[n][j]) {
            count++;
        }
    }
    
    cout << count << endl;
    
    return 0;
}