题解 | #称砝码#

本题遍历的话很好理解，动态规划主要就是要理解dp数组中要有最大重量个元素，通过dp[weight-weight[i]]->dp[weight],如果前一个可以由砝码组成一个重量的话后一个也可以，下面看代码，代码有注释。

#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int kinds;
    while(cin>>kinds){
        vector<int> weight(kinds,0);
        vector<int> quantity(kinds,0);
        int maxweight=1;
        for(int i = 0;i<kinds;i++){
            int temp;
            cin>>temp;
            weight[i]=temp;
        }//每个种类的重量
        for(int j = 0;j<kinds;j++){
            int temp;
            cin>>temp;
            quantity[j]=temp;
        }
        for(int m = 0 ;m<kinds;m++){
            maxweight+=weight[m]*quantity[m];
            
        }
        vector<bool> dp(maxweight,false);
        dp[0]=true;
        
        for(int i = 0 ;i<kinds;i++){
            for(int j = 0;j<quantity[i];j++){//因为一种重量可能有多个，
                //这里判断是不是累加起来的重量
                //也可以组成不同的重量
                
                for(int k=maxweight;k>=weight[i];k--){//这里的循环是为了统计同一重量
                    //经过累加后到底可以组成多少重量承接上一个for循环，
                    //dp中的元素值为1代表有组合可以组成这个重量
                    if(dp[k-weight[i]])
                        dp[k]=true;
                }//for3
            }//for2
        }//for1
        int cnt = 0;
        for( int i =0;i<maxweight;i++){
            if(dp[i]) cnt++;
        }
        cout<<cnt;
    }
}