题解 | 称砝码:多重背包动态规划求解

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

int main() {
    int n;
    cin >> n;
    vector<int> weights(n,0);
    vector<int> counts(n,0);
    for (int i = 0 ; i < n ;i ++) {
        cin >> weights[i];
    }
    for (int i = 0 ; i < n ;i ++) {
        cin >> counts[i];
    }
    int cnt = 1;
    int maxsum = 200000;
    vector<bool> dp(maxsum+1,false);
    dp[0] = true;
    for (int i = 0 ; i < weights.size(); i++) {
        for (int j = 0 ; j < counts[i]; j++) {
            for (int w = maxsum; w >= 0; w--) {
                if (dp[w] == true) {
                    continue;
                } else if (w >= weights[i] && dp[w - weights[i]]) {
                    cnt++;
                    dp[w] = true;
                }
            }
        }
    }
    cout << cnt;
}
// 64 位输出请用 printf("%lld")