Разделить массив на 3 части

Question

Как можно разделить массив на три части так, чтобы сумма чисел в каждом массиве не превышала сумму в остальных (В тех случаях, когда это возможно), при этом размеры массивов могут быть неодинаковыми.

Answer 1

Сумма всех элементов, деленная на 2 - s. Подгонять три части, начиная с самых больших элементов, так, чтобы сумма каждой части была меньше s. Сначала самые большие - пока можно - в одну. Потом остальные - в другую часть. Потом в третью. Оставшуюся мелочь распихивать по всем трем, как получится. Понятно, что не более чем эвристика. Но, похоже, работает - попробуйте этот код:

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;


bool exper()
{
    vector<int> v,a,b,c;
    int s = 0, sa = 0, sb = 0, sc = 0;
    for(int i = 50 + rand()%100; i-->0; )
    {
        int z = rand()%1000-50;
        s += z;
        v.push_back(z);
    }
    sort(v.begin(),v.end());
    for(auto it = v.rbegin(); it != v.rend(); it++)
    {
        int x = *it;
        if ((sa + x)*2 < s) { a.push_back(x); sa += x; }
        else if ((sb + x)*2 < s) { b.push_back(x); sb += x; }
        else if ((sc + x)*2 < s) { c.push_back(x); sc += x; }
        else return false;
    }
    if (sa < sb+sc && sb < sa+sc && sc < sa+sb) return true;
    return false;
}

int main(int argc, char * argv[])
{
    for(int tot = 0, fail = 0; ;)
    {
        fail += !exper();
        ++tot;
        cout << setw(8) << tot << "   " << fail << '\r';
    }
}

БЛОГ НА HUSL

Разделить массив на 3 части

Ответы (1 шт):