как разделить массив целых чисел на 2 подмассива и сделать их средние равными?

Question

Пожалуйста, помогите мне с вышеуказанным вопросом.Будет оценен алгоритм с рабочим примером.Также, пожалуйста, разберитесь со случаем, когда вышеописанное невозможно.

Хорошо, до сих пор у меня есть следующее:

Пройдите по всему массиву и получите среднее значение по всему массиву.На).Давайте назовем это avg

Тогда из этого среднего можно получить среднее значение всего массива, кроме a[0] (формула: avg(a[1..n-1])=(avg(a[0..n-1])*n-a[0])/(n-1)).Затем вы берете это новое среднее значение и сравниваете его с [0].Если они не равны, вы переходите к следующему значению, вычисляя средние значения из ранее известных средних по формуле сверху.

Хотя кто-то предоставил мне решение, которое «работает», я ищу наиболее эффективноеосуществление.

Answer 1

Быстрый поиск в Google вернул this .В любом случае, если вам не нужна производительность, backtracking всегда является опцией

EDIT: я пытался применить backtracking.Мое решение ни в коем случае не является эффективным.Конечно, вы можете заменить средние методы, чтобы избежать другого уровня езды на велосипеде.Кроме того, чтобы показать, что решения не существует, вы можете просто посчитать число решений.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class SOQuestion {

    /**
     * just prints a solution
     * 
     * @param list
     * @param indexes
     */
    public static void printSolution(List list, HashSet indexes) {
        Iterator iter = indexes.iterator();
        while (iter.hasNext()) {
            System.out.print(list.get((Integer) iter.next()) + " ");
        }
        System.out.println();
    }

    /**
     * calculates the average of a list, but only taking into account the values
     * of at the given indexes
     * 
     * @param list
     * @param indexes
     * @return
     */
    public static float avg(List list, HashSet indexes) {
        Iterator iter = indexes.iterator();
        float sum = 0;
        while (iter.hasNext()) {
            sum += (Integer) list.get((Integer) iter.next());
        }
        return sum / indexes.size();
    }

    /**
     * calculates the average of a list, ignoring the values of at the given
     * indexes
     * 
     * @param list
     * @param indexes
     * @return
     */
    public static float avg_e(List list, HashSet indexes) {
        float sum = 0;
        for (int i = 0; i < list.size(); i++) {
            if (!indexes.contains(i)) {
                sum += (Integer) list.get(i);
            }
        }
        return sum / (list.size() - indexes.size());
    }

    public static void backtrack(List list, int start, HashSet indexes) {
        for (int i = start; i < list.size(); i++) {
            indexes.add(i);
            if (avg(list, indexes) == avg_e(list, indexes)) {
                System.out.println("Solution found!");
                printSolution(list, indexes);
            }
            backtrack(list, i + 1, indexes);
            indexes.remove(i);
        }
    }

    public static void main(String[] args) {
        List test = new ArrayList();
        test.add(2);
        test.add(1);
        test.add(3);

        backtrack(test, 0, new HashSet());
    }
}

Answer 2

Использование алгоритма Жадности Один из подходов к проблеме, имитирующий то, как дети выбирают команды для игры, - это жадный алгоритм, который перебирает числа в порядке убывания, присваивая каждому из них любое подмножество с меньшей суммой.Это хорошо работает, когда числа в наборе имеют примерно тот же размер, что и его мощность, или меньше.

Попробуйте это в python: если среднее значение существует, тогда может найти его, в противном случае оноприблизит вас к равному среднему.

    a = [500, 1, -45, 46, -20, 100, -30, 4, 110]

    b, c = [], []

    m1, m2, n1, n2 = 0, 0, 0, 0
    count = 0
    for i in a:
        if count == 0:
            b.append(i)
            n1 += 1
            m1 = i
            n1 = 1
            count = 1
            continue
        else:
            tmp_m1 = (m1 * n1 + i) / (n1 + 1)
            tmp_m2 = (m2 * n2 + i) / (n2 + 1)
            print b, c, tmp_m1, tmp_m2
            if m1 > m2:
                if(tmp_m1 - m2 < m1 - tmp_m2):
                    b.append(i)
                    m1 = tmp_m1
                    n1 += 1
                else:
                    c.append(i)
                    m2 = tmp_m2
                    n2 += 1
            else:
                if(tmp_m1 - m2 < m1 - tmp_m2):
                    c.append(i)
                    m2 = tmp_m2
                    n2 += 1
                else:
                    c.append(i)
                    m1 = tmp_m1
                    n1 += 1
    print b, c, m1, m2

Sample output:
[500] [] 250 1
[500, 1] [] 151 -45
[500, 1, -45] [] 124 46
[500, 1, -45] [46] 108 13
[500, 1, -45, -20] [46] 106 73
[500, 1, -45, -20] [46, 100] 80 38
[500, 1, -45, -20, -30] [46, 100] 67 50
[500, 1, -45, -20, -30, 4] [46, 100] 73 85
[500, 1, -45, -20, -30, 4] [46, 100, 110] 73 73

Answer 3

#include<stdio.h>

void partitionEqualAvt(int *a, int n)
{

    int i;
    int sum=0, sSum=0, eSum, sAvg, eAvg;
    for(i=0; i<n; i++)
        sum+=a[i];
    eSum=sum;
    for(i=0; i<n-1; i++)
    {
        sAvg=0;
        eAvg=0;
        sSum+=a[i];
        eSum=sum-sSum;
        sAvg=sSum/(i+1);
        eAvg=eSum/(n-i-1);
        if(sAvg == eAvg)
        {
            printf("\nAverage = %d from [%d to %d] and [%d to %d]", sAvg, 0, i, i+1, n);
        }
    }
}

int main()
{

    int a[]={1,1,1,1,1,1};
    int n=sizeof(a)/sizeof(int);
    partitionEqualAvt(a,n);
    return 0;
}

Answer 4

Я думаю, что если сумма всех элементов в исходном массиве нечетна, то разделение на 2 массива невозможно.как бы то ни было, если sum == even, вы можете начать делать свой массив таким, чтобы сумма элементов в каждом == SUM / 2

Answer 5

Попробуйте этот код ...

#include <QList>
#include <QDebug>

/****

We sort the array in the desending order. So the first two elemnts
are the biggest element of the array. These are put in split1 and the
split2 array. Note that we start from the biggest element the average
is going to be much higher than the final avarage. Next we start placing
the smaller elemnts from source to split1 or split2. To do this we make a
simple dicision. We look at the value to be added and then see if that will
increase/decrease the average of a given split. Accordingly we make our
decesion.

****/


static bool averageSplit(const QList<int>& source,
                         QList<int>& split1,
                         QList<int>& split2)
{
    if (source.size() < 2) {
        return false;
    }

    QList<int> list = source;
    qSort(list.begin(), list.end(), qGreater<int>());

    double sum = 0;
    foreach(int elm, list) {
        sum += elm;
    }
    const double totalAvg = sum / list.size();

    double sum1 = list[0];
    double sum2 = list[1];
    split1.append(list[0]);
    split2.append(list[1]);
    for(int i = list.size() - 1; i >= 2; --i) {
        double avg1 = sum1 / split1.size();
        double avg2 = sum2 / split2.size();
        int val = list[i];
        if (avg1 < avg2) {
            // Try to increase tha avg1 or decrease avg2.
            if (val > split1.size()) {
                split1.append(val);
                sum1 += val;
            }
            else {
                split2.append(val);
                sum2 += val;
            }
        }
        else {
            // Try to increase tha avg2 or decrease avg1.
            if (val > split2.size()) {
                split2.append(val);
                sum2 += val;
            }
            else {
                split1.append(val);
                sum1 += val;
            }
        }
    }

    qDebug() << "totalAvg " << totalAvg;
    qDebug() << "Avg1 " << sum1 / split1.size();
    qDebug() << "Avg2 " << sum2 / split2.size();
}

void testAverageSplit()
{
    QList<int> list;

    list << 100 << 20 << 13 << 12 << 12 << 10 << 9 << 8 << 6 << 3 << 2 << 0;
    list << -1 << -1 << -4 << -100;

    QList<int> split1;
    QList<int> split2;
    averageSplit(list, split1, split2);

    qDebug() << "split1" << split1;
    qDebug() << "split2" << split2;
}

Answer 6

Вот как я это сделал:
1 - Общий массив -> если нечетное число, то не может создать два отдельных массива.O (n)
2 - Разделите общее число на 2.
3 - Массив сортировки (от верхнего к низшему) -> O (NLogN) * ​​1004 * 4 - Начните с наибольшего числа и продолжайте пытаться получить оставшиесясумма, перейдя к следующему наибольшему числу.Если вы не можете сделать это, переместите число в другой массив.-> Я думаю, что худший случай - это O (N ^ 2).

Итак, давайте возьмем этот пример: 3, 19, 7, 4, 6, 40, 25, 8

1. Всего = 112
   
2. Разделить на 2 = 56
   
3. Массив сортировки - 3, 4, 6, 7, 8, 19, 25, 40
   
4. -> 40 в списке 1 (всего список 1 = 40, осталось 16)
   -> 25 слишком велико, в списке 2 (всего список 2 = 25)
   -> 19 слишком велико, в списке 2 (всего список 2 = 44)
   -> тестирование 8 в списке 1 (всего список 1 = 48, осталось 8)
   -> Тестирование 7 в списке 1 (список 1всего = 55, осталось 1)
   -> нет способа добавить еще 1
   -> 7 не проходит тест 6 (список 1 всего = 54, осталось 2)
   -> нет способа добавить 2больше
   -> 6 не проходит тест 4 (всего список 2 - 52, осталось 4)
   -> нет способа добавить еще 2
   -> 4 не проходит тест 3
   -> 3не удается вернуться к 8
   -> Переместить 8 в список 2 и начать тестирование 7 (всего список 1 = 47, осталось 9, всего список 2 = 52)
   -> Тестирование 6 (всего список 1 = 53, Осталось 3)
   -> Добавить 3 элемента (Всего 1 список = 56, успех)
   

Итак, два списка [40,7,6,3] и [25,19,8,4]