题解 | #称砝码#

称砝码

http://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c

题目的主要信息：

现有一组砝码，重量互不相等，分别为 $m_{1}$ , $m_{2}$ , $m_{3}$ … $m_{n}$ ；
每种砝码对应的数量为 $x_{1}$ , $x_{2}$ , $x_{3}$ ... $x_{n}$ 。

求解这些砝码能组合出多少种不同的重量。需要注意的是，称重重量包括 0 。

方法一：

采用动态规划。用weights储存不同的砝码重量，nums储存不同重量砝码的数量。maxw表示所有砝码加起来的重量，dp为动态数组，dp[i]=1表示重量i可以用砝码组合出来，dp[i]=0表示重量i不能用砝码组合出来。

用三层for循环对dp数组进行更新，第一层对所有不同重量的砝码进行遍历，第二层对相同重量的砝码个数进行遍历，第三层对重量进行遍历，如果dp[k-weights[i]]==1，就说明不用到当前的砝码可以组成重量k-weights[i]，加上当前遍历的砝码可以组成重量k，因此置dp[k]=1。最后遍历一遍dp数组，统计有多少个值为1，则是砝码能组成的重量个数。

具体做法：

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

int main(){
    int n;
    while(cin>>n){
        vector<int> weights;
        int tmp;
        for(int i=0; i<n; i++){//输入砝码的重量
            cin>>tmp;
            weights.push_back(tmp);
        }
        vector<int> nums;
        for(int i=0; i<n; i++){//输入每个砝码的数量
            cin>>tmp;
            nums.push_back(tmp);
        }
        int maxw = 0;//最大重量
        for(int i=0; i<n; i++){//最大重量为所有砝码重量之和
            maxw += nums[i]*weights[i];
        }
        
        vector<int> dp(maxw+1,0);
        dp[0]=1;//初始化为0
        //动态规划
        for(int i=0; i<n; i++){//遍历每个不同重量的砝码
            for(int j=0; j<nums[i]; j++){//遍历每个砝码的数量
                for(int k=maxw; k>=weights[i]; k--){//遍历所有重量
                    if(dp[k-weights[i]]){//如果k-weights[i]重量可以组成的话，那k重量也可以组成的
                        dp[k]=1;
                    }
                }
            }
        }
        int res = 0;
        for(int i=0; i<=maxw; i++){
            if(dp[i]==1){
                res++;
            }
        }
        cout<<res<<endl;
    }
    
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，砝码的重量和数量是有限制的，相当于常数级别，因此三重循环的时间复杂度为 $O (n)$ 。
空间复杂度： $O (n)$ ，借用了dp数组的空间。

方法二：

用集合的方法。vec中储存所有砝码，包括相同数量的砝码，用集合s保存所有可能组成的重量。遍历一遍所有砝码，把它加到集合中已组成出的重量中，组合出新的重量，根据集合的性质，若新组合出的重量在集合中没有出现，该重量会更新到s集合中。最后s集合的大小即为可以组成出的重量的个数。 alt 具体做法：

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    while(cin>>n){
        vector<int> vec,weights;
        int temp;
        for(int i =0; i< n;i++){
            cin>>temp;
            weights.push_back(temp);//保存砝码重量
        }
        for(int i= 0; i< n;i++){
            cin>>temp;
            for(int j=0; j< temp;j++){
                vec.push_back(weights[i]);//所有砝码，包括相同重量的多个砝码
            }
        }
        set<int> s;//集合中储存所有可以组合出的重量
        s.insert(0); //0也算是一个初始重量
        for(int i=0; i< vec.size();i++){//遍历一遍所有砝码
            set<int> t=s;
            for(auto it=t.begin();it!=t.end();it++){//把砝码重量加到原本可以组成出的重量上，得到新的重量
                s.insert(*it+vec[i]);
            }
        }
        cout<<s.size()<<endl;
    }
    return 0;
}

复杂度分析：