题解 | #称砝码#

法1 回溯法，超时

void dfs(vector<pair<int,int>> fama,int num,int sum){
    tb.insert(sum);
    for(int i=0;i<fama.size();++i){
        if(fama[i].second!=0){
            sum+=fama[i].first;
            fama[i].second--;
            dfs(fama,num-1,sum);
            sum-=fama[i].first;
            fama[i].second++;
        }
    }
}

法2

考虑到每次加砝码，已有的每个重量（保存在unordered_set中的）都会增加一个砝码重量值。

因此对每个砝码，将保存在unordered_set中的重量加上砝码重量，并放入集合中自动去重。

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> weight(n);
    vector<int> num(n);
    for(int i=0;i<n;++i)
        cin >> weight[i];
    for(int i=0;i<n;++i)
        cin >> num[i];
    unordered_set<int> table;
    table.insert(0);
    for(int i=0;i<n;++i){
        for(int j=0;j<num[i];++j){
            unordered_set<int> temp(table);
            for(auto it=temp.begin();it!=temp.end();++it){
                table.insert(*it+weight[i]);
            }
        }
    }
    cout << table.size();
}
// 64 位输出请用 printf("%lld")

法3 动态规划 0-1背包

递推公式：

if(dp[j-fama[i]) dp[j]=true;

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> weight(n);
    vector<int> num(n);
    for(int i=0;i<n;++i)
        cin >> weight[i];
    for(int i=0;i<n;++i)
        cin >> num[i];
    vector<int> fama;
    int allW=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<num[i];++j){
            fama.push_back(weight[i]);
            allW+=weight[i];
        }
    }
    n=fama.size();
    vector<bool> dp(allW+1,false);
    sort(fama.begin(),fama.end());
    dp[0]=true;
    for(int i=0;i<n;++i){
        for(int j=allW;j>=fama[i];--j){
            if(dp[j-fama[i]])
                dp[j]=true;
        }
    }
    int x=0;
    for(int i=0;i<=allW;++i){
        if(dp[i])
            ++x;
    }
    cout << x;
}
// 64 位输出请用 printf("%lld")