题解 | #称砝码#完全背包问题简洁版

#include <iostream>
#include <vector>
using namespace std;
vector<int> w;
vector<int> v;
vector<vector<bool>> f;

int main()
{
    int n;
    cin >> n;
    w.resize(n + 1);
    v.resize(n + 1);
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++) cin >> v[i];
    int m = 0;
    for(int i = 1; i <= n; i++) m += w[i] * v[i];
    f.resize(n + 1, vector<bool> (m + 1, false));
    for(int i = 0; i <= n; i++) f[i][0] = true;

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k <= v[i] && k * w[i] <= j; k++)
                f[i][j] = f[i][j] | f[i-1][j-k*w[i]];
    int ans = 0;
    for(int j = 0; j <= m; j++)
        if(f[n][j])
            ans++;
    cout << ans << endl;
    return 0;
}