题解 | #数组分组# 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;
}
投递华为HUAWEI等公司8个岗位
阿里云工作强度 727人发布