题解 | #称砝码#

称砝码

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 求解
例子
3
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";
    }
}



全部评论

相关推荐

许愿ssp的咸鱼很不想泡池子:import python as pyhton
点赞 评论 收藏
分享
评论
3
3
分享

创作者周榜

更多
牛客网
牛客企业服务