题解 | #称砝码#

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

void dfs(unordered_set<int>& res,vector<int>& m, vector<int> used,int index,int sum)
{
    if(index == used.size())
    {
        res.insert(sum);
        return;
    }
    for(int i = index; i < used.size(); i++)
    {
        for(int j = 0; j <= used[i]; j++)
        {
            used[i] -= j;
            dfs(res,m,used,index+1,sum+j*m[i]);
            used[i] += j;
        }
    }
    
}

int main()
{
    //1.先处理输入吧
    int n ;
    cin >> n;
    vector<int> m(n);
    vector<int> x(n);
    int sum = 0;//所有砝码的总重量
    for(int i = 0; i < n; i++)
    {
        cin >> m[i];
    }
    for(int i = 0; i < n; i++)
    {
        cin >> x[i];
        sum += x[i] * m[i];
    }
    //2.debug查看输入数据是否准确保存
//     for(int i = 0; i < n; i++)
//     {
//         cout << m[i] << " ";
//     }
//     cout << endl;
//     for(int i = 0; i < n; i++)
//     {
//         cout << x[i] << " ";
//     }
    //3.计算可以称出来的不同的重量数
    int count = 0;
//     unordered_set<int> res;
//     res.insert(0);
//     vector<int> used = x;
    //dfs(res,m,used,0,0);
    
    vector<int> dp(sum+1,0); 
    dp[0] = 1;
    dp[sum] = 1;
    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= x[i]; j++)
        {
            for(int k = sum; k >= m[i]; k--)
            {
                if(dp[k - m[i]])
                {
                    dp[k] = 1;
                }
            }
        }
    }
    
    for(int i = 0; i <= sum; i++)
    {
        if(dp[i])
        {
            count++;
        }
    }
    
    //4.处理输出
    cout << count << endl;
    
    
    return 0;
}

参考01背包

// C++ Version
for (int i = 1; i <= n; i++)
  for (int l = W; l >= w[i]; l--) f[l] = max(f[l], f[l - w[i]] + v[i]);