时间戳

首页 > 解决方案 > 将数组分成两个相等的部分，差异最小并找到每个部分的总和

arrays - 将数组分成两个相等的部分，差异最小并找到每个部分的总和

问题描述

嗨，我正在尝试用蛮力解决问题，但我无法解决如何解决它。我试了几个小时。

考虑一个数组 inputArray，其中至少有两个非零正整数，范围在 1 到 300 之间。根据这些规则将阵列器分成两组。

  1. 每个整数应该属于两个组之一
  2. 每个组中的整数总和必须尽可能接近相等。
  3. 2 组之间的整数总数之差不应超过 1

我需要返回每组的总和

标签： arraysalgorithmdata-structuressuminteger

解决方案

我使用 c++ 解决了这个问题

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int ans(int i,int n,float s)
{
  if(i<n-1) return INT_MAX;
  if(n==0) return abs(s);
  return min(ans(i-1,n-1,s-v[i-1]),ans(i-1,n,s));
}
 
int main()
{
  string s;
  cin>>s;
  int c=0;
  for(int i=0;i<s.length();i++)
  {
    if(s[i]==',') {v.push_back(stoi(s.substr(c,i-c)));
    c=i+1;}
  }
  v.push_back(stoi(s.substr(c,s.length()-c)));
   //for(int i=0;i<v.size();i++) cout<<v[i];
  int ss=0;
  for(int i=0;i<v.size();i++) ss+=v[i];
  int n1=v.size();
  int n2=n1/2;
  float su=ss/2;
  int k=ans(n1-1,n2,su);
  cout<<ss-su-k<<" "<<su+k;
 
}

这是解决方案，希望对您有所帮助

输出图像

推荐阅读