题解 | #称砝码#

称砝码

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

题意：有n种不同重量的砝码，每种砝码的数量不一定相同，问从这些砝码中选出一些砝码放在秤上能有多少种不同的重量

1.暴力求解

由题意可知需要求出不同重量的种数，这需要将不同砝码重量相加起来，使用回溯法

将每个砝码都看作成一个物品，将每个砝码用几个的情况都去dfs走一遍，然后使用map记录重量个数

但是这种方***超时，dfs外层循环依赖不同砝码个数，内层需要使用该砝码的个数 , 时间复杂度 $O(n*x)$

用到的空间主要是记录不同重量的map，这里可以考虑极端情况，10种不同的砝码，每个数量为10个, 每个重量为2000， $100 * 2000 = 200000$ ，这是最大重量情况

空间复杂度不会超过 $O(n*x*m)$ ,

#include<bits/stdc++.h>
using namespace std;
int n, a[10], b[10];
map<int, int> mp;
void dfs(int x, int y) {
    int sum = 0;
    mp[y] = 1;
    if(x == n) return;
    dfs(x + 1, y);
    for(int i = 0 ; i < b[x] ;  i++) {
        sum += a[x];
        dfs(x + 1, y + sum);
    }
}
int main() {
    while(cin >> n) {
        mp.clear();
        for(int i = 0 ; i < n ; i++) {
            cin >> a[i];
        }
        for(int i = 0 ; i < n ; i++) {
            cin >> b[i];
        }
        dfs(0, 0);
        cout << mp.size() << "\n";
    }
}

2. set 求解

例子

1 2 4

4 2 1

从下图中就能看出重量为2重复两次，重量为4重复三次，这还只是少数砝码情况

我们再来考虑上面超时的问题，本质上是因为我们所有的情况都去dfs跑了一遍，但是上面也计算过不同重量的数量不会超过200000，说明我们有很大一部分重复了,

现在要考虑有什么办法记录没有重复的重量然后做有意义的计算，可以考虑使用set结构将重量去重，每次将砝码和当前的重量相加得到新的不同的重量集合

可知不同重量不会超过200000，最多只有100个砝码，时间复杂度为 $O(n*x*(n*x*m*))$

空间复杂度同暴力求解

#include<bits/stdc++.h>
using namespace std;
int n, a[10], b[10];
set<int> st1, st2;
int main() {
    while(cin >> n) {
        st1.clear();
        for(int i = 0 ; i < n ; i++) {
            cin >> a[i];
        }
        for(int i = 0 ; i < n ; i++) {
            cin >> b[i];
        }
        st1.insert(0);
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < b[i] ; j++) {
                set<int>::iterator iter = st1.begin();
                while (iter!=st1.end()) {
                    st2.insert(*iter);
                    st2.insert(*iter + a[i] * (j + 1));
                    iter++;
                }
            }
            st1.swap(st2);
            st2.clear();
        }
        cout << st1.size() << "\n";
    }
}

3. bitset求解

这里的bitset主要用于优化上述的set结构，bitset是一个使用二进制位标记的结构,使用二进制的按位或和左移操作能够省略掉遍历所有元素的操作，时间复杂度大大降低

因为这里使用的也是二进制位标记，空间从单位为 int 变为 bit，空间复杂度也大大降低

时间复杂度变为 $O(n*x)$

空间复杂度变为 $O(n*x*m*bit)$

#include<bits/stdc++.h>
using namespace std;
int n, a[10], b[10];
bitset<200005> st1, st2;
int main() {
    while(cin >> n) {
        st1.reset();
        for(int i = 0 ; i < n ; i++) {
            cin >> a[i];
        }
        for(int i = 0 ; i < n ; i++) {
            cin >> b[i];
        }
        st1.set(0);
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < b[i] ; j++) {
                st2 = st1 << a[i];
                st1 = st1 | st2; 
                st2.reset();
            }
        }
        cout << st1.count() << "\n";
    }
}