题解 | 称砝码

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    cin >> n;
  
    vector<int> w(n+5,0),cnt(n+5,0);
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=n;i++)cin>>cnt[i];
    
    unordered_map<int,int> dp;
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        vector<int> t;
        for(auto x:dp)
        {
           int val=x.first;
           for(int j=1;j<=cnt[i];j++){
            t.push_back(val+j*w[i]);
           }
        }
        for(int val:t)
        {
            dp[val]=1;
        }
    }
  cout<<dp.size()<<endl;
    return 0;
}

#牛客春招刷题训练营#https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fwww.nowcoder.com%2Fdiscuss%2F726480854079250432

/*很经典的多重背包，好就没写了。就有些吃力了。这题set，map都可以，因为数据有点大，

所以数组肯定存不了那么大的下标，所以我们采取哈希，也就是map。首先是dp[0]=1，这算一种。

然后再依次遍历每组的w[i]的倍数，把dp里面已经有的数跟这些重量塞进一个临时的vector。

然后再把vector,t的每个数值标记为1.你要是map的键值搞bool类型也阔以。最后输出大小就行

*/