题解 | #称砝码#
称砝码
http://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
题意:有n种不同重量的砝码,每种砝码的数量不一定相同,问从这些砝码中选出一些砝码放在秤上能有多少种不同的重量
1.暴力求解
由题意可知需要求出不同重量的种数,这需要将不同砝码重量相加起来,使用回溯法
将每个砝码都看作成一个物品,将每个砝码用几个的情况都去dfs走一遍,然后使用map记录重量个数
但是这种方***超时,dfs外层循环依赖不同砝码个数,内层需要使用该砝码的个数 , 时间复杂度
用到的空间主要是记录不同重量的map,这里可以考虑极端情况,10种不同的砝码,每个数量为10个, 每个重量为2000,
,这是最大重量情况
空间复杂度不会超过
,
#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 求解
例子
3
1 2 4
4 2 1
从下图中就能看出重量为2重复两次,重量为4重复三次,这还只是少数砝码情况
我们再来考虑上面超时的问题,本质上是因为我们所有的情况都去dfs跑了一遍,但是上面也计算过不同重量的数量不会超过200000,说明我们有很大一部分重复了,
现在要考虑有什么办法记录没有重复的重量然后做有意义的计算,可以考虑使用set结构将重量去重,每次将砝码和当前的重量相加得到新的不同的重量集合
可知不同重量不会超过200000,最多只有100个砝码, 时间复杂度为
空间复杂度同暴力求解
#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, 空间复杂度也大大降低
时间复杂度变为
空间复杂度变为
#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"; } }