题解 | #称砝码#

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> m(n,0);
        vector<int> x(n,0);
        set<int> s;
        s.insert(0);

        for (int i = 0; i < n; i++)
            cin >> m[i];
        for (int i = 0; i < n; i++)
            cin >> x[i];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < x[i]; j++) {
                set<int> t(s);
                for (auto it = t.begin(); it != t.end(); it++) {
                    s.insert(*it+m[i]);
                }
                // cout << s.size() << endl;
            }
        }

        cout << s.size() << endl;
    }
}

复制了一位大佬newcoder的题解：先计算可能的最大值sum，砝码总数len 则建立dp[len+1][sum+1] 表示第i号砝码之前能否凑出重量j 注意len不是类别的数量而是砝码的数量 之后就按照0-1背包思路dp，再设置一个unordered_set，当j被成功凑出后便加入集合 最后输出集合的大小(再额外加一个0）

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int main(){
    int N;
    while(cin>>N){
        vector<int> weight;
        vector<int> mount;
        int temp;
        for(int i=0;i<N;i++){
            cin>>temp;
            weight.emplace_back(temp);
        }
        for(int i=0;i<N;i++){
            cin>>temp;
            mount.emplace_back(temp);
        }
        int sum=0;
        for(int i=0;i<N;i++){
            sum=sum+weight[i]*mount[i];
        }
        vector<int> Weight;
        for(int i=0;i<N;i++){
            for(int j=0;j<mount[i];j++){
                Weight.emplace_back(weight[i]);
            }
        }
        int len=Weight.size();
        unordered_set<int> ok;
        vector<vector<bool>> dp(len+1,vector<bool>(sum+1, false));
        for(int i=0;i<len+1;i++){
            dp[i][0]=true;
        }
        for(int i=1;i<len+1;i++){
            for(int j=1;j<sum+1;j++){
                if(Weight[i-1]>j){
                    dp[i][j]=dp[i-1][j];
                }
                else{
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-Weight[i-1]];
                }
                if(dp[i][j]){
                     ok.insert(j);
                }
            }
        }
        
        cout<<ok.size()+1<<endl;
    }
    return 0;
}