题解 | #称砝码# 0-1背包问题 动态规划

思路：

先计算可能的最大值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;
}