题解 | #数组分组# 01背包+处理负数越界

数组分组

https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86

看了取值和数组大小,是可以用01背包做的。讲的人比较少,那我把自己的ac代码分享一下。
思路:

1)考虑把3和5的倍数分别求和(sum_3和sum_5)之后,剩下部分的元素(arro)求和(sum_left)// 时间复杂度o(n);
剩下的问题是:要从arro中挑选一部分元素出来放入5的数组中,它们的和为x。根据题意可以得到:
sum_5+x=sum_3+sum_left-x;
== > tar=(sum_3+sum_left-sum_5) / 2;这就是背包问题的目标和
然后解决一些特殊情况(line26-32)

2)转化为01背包问题 // 时间复杂度o(mk),m是子数组大小,k=sum_max;
这里做法和01是一样的,只需要解决负数越界的问题。
越界有向前向后两种,向前的需要提前计算一个偏移量offset,向后计算一个最大值sum_max;
然后注意初始化和最后返回答案时,恢复偏移量就行,中间过程和01背包一致。
btw,由于存在负数,不能用倒序遍历来优化空间复杂度的方法。


#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

int n;
int arr[50];

bool func(){
    vector<int> arro;
    int sum_5=0, sum_3=0, sum_left=0; // sum_left:非3和5的倍数的数之和
    int sum_max=0, offset=0; // 考虑负数导致的越界,计算前后的偏移量
    for(int i=0;i<n;i++){
        int x=arr[i];
        if(x%5==0) sum_5+=x;
        else if(x%3==0) sum_3+=x;
        else {
            sum_left+=x;
            sum_max+=abs(x);
            offset+=x>=0? 0: abs(x);
            arro.push_back(x);
        }
    }
    
    int tar=(sum_3+sum_left-sum_5)/2;
    if(2*tar!=sum_3+sum_left-sum_5) return false;
    if(arro.size()==0){
        return tar==0;
    }else if(arro.size()==1){
        return tar==0||tar==arro[0];
    }
    
    // 01背包部分,对数组的和加了偏移量offset
    int m=arro.size();
    vector<vector<int>> d(m+1, vector<int>(sum_max+1, 0));
    d[0][offset]=true;
    for(int i=1;i<=m;i++){
        int x=arro[i-1];
        for(int j=sum_max;j>=0;j--){
            d[i][j]=d[i-1][j];
            if(j-x>sum_max||j-x<0) continue;
            d[i][j]=d[i][j]||d[i-1][j-x];
        }
    }
    
    return d[m][tar+offset];
}

int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    if(func()) cout<<"true\n";
    else cout<<"false\n";
    
    return 0;
}



全部评论

相关推荐

吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客企业服务