Как оптимально разделить массив на два подмассива так, чтобы сумма элементов в обоих была одинаковой, иначе выдает ошибку?

Question

Как оптимально разделить массив на два подмассива так, чтобы сумма элементов в обоих подмассивах была одинаковой, иначе выдает ошибку?

Пример 1

Учитывая массив

10,  20 , 30 , 5 , 40 , 50 , 40 , 15

Его можно разделить на

10, 20, 30, 5, 40

и

50, 40, 15

Каждый подмассив суммирует до 105.

Пример 2

10,  20,  30,  5,  40,  50,  40,  10

Массив нельзя разделить на 2 массива равной суммы.

Answer 1

@ Задача суммы подмножества Гал является NP-полной и имеет O (n * TotalSum) псевдополиномиальный алгоритм динамического программирования.Но эта проблема не NP-Complete.Это особый случай, и на самом деле его можно решить за линейное время.

Здесь мы ищем индекс, в котором мы можем разбить массив на две части с одинаковой суммой.Проверьте следующий код.

Анализ: O (n), поскольку алгоритм выполняет итерацию только через массив и не использует TotalSum.

public class EqualSumSplit {

    public static int solution( int[] A ) {

        int[] B = new int[A.length];
        int[] C = new int[A.length];

        int sum = 0;
        for (int i=0; i< A.length; i++) {
            sum += A[i];
            B[i] = sum;
            // System.out.print(B[i]+" ");
        }   
        // System.out.println();

        sum = 0;
        for (int i=A.length-1; i>=0; i--) {
            sum += A[i];
            C[i] = sum;
            // System.out.print(C[i]+" ");
        }
        // System.out.println();

        for (int i=0; i< A.length-1; i++) {
            if (B[i] == C[i+1]) {
                System.out.println(i+" "+B[i]);
                return i;
            }
        }

        return -1;

    }

     public static void main(String args[] ) {
         int[] A = {-7, 1, 2, 3, -4, 3, 0};
         int[] B = {10, 20 , 30 , 5 , 40 , 50 , 40 , 15};        
         solution(A);
         solution(B);
     }

}

Answer 2

Мне задали этот вопрос в интервью, и я дал ниже простое решение, поскольку я НЕ видел эту проблему ни на одном веб-сайте ранее.

Допустим, Array A = {45,10,10,10, 10,5} Тогда разделение будет с индексом = 1 (индекс на основе 0), так что у нас будет два равных набора сумм {45} и {10,10,10,10,5}

int leftSum = A[0], rightSum = A[A.length - 1];
int currentLeftIndex = 0; currentRightIndex = A.length - 1

/ * Переместите два указателя указателя к середине массива до currentRightIndex! = CurrentLeftIndex.Увеличьте leftIndex, если сумма левых элементов по-прежнему меньше или равна сумме элементов справа от 'rightIndex'. В конце проверьте, оставлен ли leftSum == rightSum.Если true, мы получили индекс как currentLeftIndex + 1 (или просто currentRightIndex, так как currentRightIndex будет равен currentLeftIndex + 1 в этом случае).* /

while (currentLeftIndex < currentRightIndex)
{
if ( currentLeftIndex+1 != currentRightIndex && (leftSum + A[currentLeftIndex + 1)     <=currentRightSum )
{
 currentLeftIndex ++;
 leftSum = leftSum + A[currentLeftIndex];
}


if ( currentRightIndex - 1 != currentLeftIndex && (rightSum + A[currentRightIndex - 1] <= currentLeftSum)
{
 currentRightIndex --;
 rightSum = rightSum + A[currentRightIndex];
}

}

if (CurrentLeftIndex == currentRightIndex - 1 && leftSum == rightSum)
PRINT("got split point at index "+currentRightIndex);

Answer 3

public class Problem1 {

public static void main(String[] args) throws IOException{
    Scanner scanner=new Scanner(System.in);
    ArrayList<Integer> array=new ArrayList<Integer>();
    int cases;
    System.out.println("Enter the test cases");
    cases=scanner.nextInt();

    for(int i=0;i<cases;i++){
        int size;


        size=scanner.nextInt();
        System.out.println("Enter the Initial array size : ");

        for(int j=0;j<size;j++){
            System.out.println("Enter elements in the array");
            int element;
            element=scanner.nextInt();
            array.add(element);
        }
    }

    if(validate(array)){
System.out.println("Array can be Partitioned");}
  else{
     System.out.println("Error");}

}

public static boolean validate(ArrayList<Integer> array){
    boolean flag=false;
    Collections.sort(array);
    System.out.println(array);
    int index=array.size();

    ArrayList<Integer> sub1=new ArrayList<Integer>();
    ArrayList<Integer> sub2=new ArrayList<Integer>();

    sub1.add(array.get(index-1));
    array.remove(index-1);

    index=array.size();
    sub2.add(array.get(index-1));
    array.remove(index-1);

    while(!array.isEmpty()){

    if(compareSum(sub1,sub2)){
        index=array.size();
        sub2.add(array.get(index-1));
        array.remove(index-1);
    }
    else{
        index=array.size();
        sub1.add(array.get(index-1));
        array.remove(index-1);
    }   
    }

    if(sumOfArray(sub1).equals(sumOfArray(sub2)))
        flag=true;
    else
        flag=false;

    return flag;
}

public static Integer sumOfArray(ArrayList<Integer> array){
    Iterator<Integer> it=array.iterator();
    Integer sum=0;
    while(it.hasNext()){
        sum +=it.next();
    }

    return sum;
}

public static boolean compareSum(ArrayList<Integer> sub1,ArrayList<Integer> sub2){
    boolean flag=false;

    int sum1=sumOfArray(sub1);
    int sum2=sumOfArray(sub2);

    if(sum1>sum2)
        flag=true;
    else
        flag=false;

    return flag;
}

}

// Жадный подход //

Answer 4

Эта проблема говорит о том, что если массив может иметь два подмассива с одинаковой суммой элементов.Таким образом, логическое значение должно быть возвращено.Я нашел эффективный алгоритм: Алго: Процедура Шаг 1: Возьмите пустой массив в качестве контейнера, отсортируйте исходный массив и сохраните в пустом.Шаг 2: теперь возьмите два динамически распределяемых массива и извлеките самый высокий и второй самый высокий из вспомогательного массива и сохраните его в двух подмассивах соответственно и удалите из вспомогательного массива.Шаг 3: Сравните сумму элементов в подмассивах, меньшая сумма будет иметь шанс получить самый высокий оставшийся элемент в массиве, а затем удалить из контейнера.Шаг 4: Повторяйте шаг 3, пока контейнер не опустеет.Шаг 5: Сравните сумму двух подмассивов, если они совпадают, возвращают true, иначе false.

// Сложность этой проблемы заключается в том, что может быть много комбинаций, но у этого алгоритма есть один уникальный способ.

Answer 5

очень простое решение с рекурсией

public boolean splitArray(int[] nums){
            return arrCheck(0, nums, 0);
        }

public boolean arrCheck(int start, int[] nums, int tot){
            if(start >= nums.length) return tot == 0;
            if(arrCheck(start+1, nums, tot+nums[start])) return true;
            if(arrCheck(start+1, nums, tot-nums[start])) return true;
            return false;
        }

Answer 6

Найденное решение здесь

package sort;

import java.util.ArrayList;
import java.util.List;

public class ArraySumSplit {

public static void main (String[] args) throws Exception {

    int arr[] = {1 , 2 , 3 , 4 , 5 , 5, 1, 1, 3, 2, 1};
    split(arr);

}

static void split(int[] array) throws Exception {
    int sum = 0;
    for(int n : array) sum += n;
    if(sum % 2 == 1) throw new Exception(); //impossible to split evenly
    List<Integer> firstPart = new ArrayList<Integer>();
    List<Integer> secondPart = new ArrayList<Integer>();
    if(!dfs(0, sum / 2, array, firstPart, secondPart)) throw new Exception(); // impossible to split evenly;
    //firstPart and secondPart have the grouped elements, print or return them if necessary.
    System.out.print(firstPart.toString());
    int sum1 = 0;
    for (Integer val : firstPart) {
        sum1 += val;
    }
    System.out.println(" = " + sum1);

    System.out.print(secondPart.toString());
    int sum2 = 0;
    for (Integer val : secondPart) {
        sum2 += val;
    }
    System.out.println(" = " + sum2);
}

static boolean dfs(int i, int limit, int[] array, List<Integer> firstPart, List<Integer> secondPart) {
    if( limit == 0) {
        for(int j = i; j < array.length; j++) {
            secondPart.add(array[j]);
        }
        return true;
    }
    if(limit < 0 || i == array.length) {
        return false;
    }
    firstPart.add(array[i]);
    if(dfs(i + 1, limit - array[i], array, firstPart, secondPart)) return true;
    firstPart.remove(firstPart.size() - 1);

    secondPart.add(array[i]);
    if(dfs(i + 1, limit, array, firstPart, secondPart)) return true;
    secondPart.remove(secondPart.size() - 1);
    return false;
}
}

Answer 7

Алгоритм:

Шаг 1) Разделить массив на два
Шаг 2) Если сумма равна, разделение завершено
Шаг 3) Поменять один элемент из массива1 на массив2, руководствуясьчетыре правила:
ЕСЛИ сумма элементов в массиве1 меньше суммы элементов в массиве2
Правило1:
Найти число в массиве1, которое меньше, чем число в массиве2, таким образом, что обменэти элементы не увеличивают сумму array1 сверх ожидаемой суммы.Если найдено, поменяйте местами элементы и верните.
Правило2:
Если Правило1 не удовлетворено, найдите число в массиве 1, которое больше, чем число в массиве 2, таким образом, чтобы разница между любыми двумя числами вarray1 и array2 не меньше, чем разница между этими двумя числами.
ELSE
Rule3:
Найти число в массиве1, которое больше, чем число в массиве2, таким образом, чтобы обменять эти элементы неуменьшить сумму массива1 сверх ожидаемой суммы.Если найдено, поменяйте местами элементы
и верните.
Правило4:
Если правило 3 не удовлетворено, найдите число в массиве 1, которое меньше числа в массиве 2 таким образом, чтобы разница междудва числа в массивах array1 и array2 не меньше, чем разница между этими двумя числами.
Шаг 5) Переходите к шагу 2, пока в результате подкачки не будет получен массив с таким же набором элементов, который уже встречался Setp 6) Если происходит повторение, этомассив не может быть разбит на две половины с равной суммой.Текущий набор массивов ИЛИ набор, сформированный непосредственно перед этим повторением, должен быть лучшим разбиением массива.

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

Java-программа доступна по адресу Java Code

Answer 8

Эта функция разделит и уравновесит список чисел, равных по сумме, если сумма четна.

Python3 solution:

def can_partition(a):
    mylist1 = []
    mylist2 = []
    sum1 = 0
    sum2 = 0

    for items in a:
        # Take total and divide by 2.
        total = sum(a)
        if total % 2 == 0:
            half = total//2
        else:
            return("Exiting, sum has fractions, total %s half %s" % (total, total/2))       
        mylist1.append(items)
    print('Total is %s total, half is %s' %(total, total/2))

    for i in a:
        sum1 = sum(mylist1)
        sum2 = sum(mylist2)
        if sum2 < half:
            mypop = mylist1.pop(0)
            mylist2.append(mypop)

    # Function to swtich numbers between the lists if sums are uneven.           
    def switchNumbers(list1, list2,switch_diff):
        for val in list1:
            if val == switch_diff:
                val_index = list1.index(val)
                new_pop = list1.pop(val_index)
                list2.append(new_pop)

    #Count so while do not get out of hand 
    count = len(a)       
    while count != 0: 
        sum1 = sum(mylist1)
        sum2 = sum(mylist2)
        if sum1 > sum2:
            diff = sum1 -half
            switchNumbers(mylist1, mylist2, diff)
            count -= 1
        elif sum2 > sum1:
            diff = sum2 - half
            switchNumbers(mylist2, mylist1, diff)
            count -= 1
        else:
            if sum1 == sum2:
                print('Half sum1 sum2 :',half, sum1,sum2)
                break
        count -= 1

    return (mylist1, mylist2)

b = [ 2, 3, 4, 2, 3, 1, 2, 5, 4, 4, 2, 2, 3, 3, 2 ]
can_partition(b)

Output:
Total is 42 total, half is 21.0
Half sum1 sum2 : 21 21 21

([4, 4, 2, 2, 3, 3, 2, 1], [2, 3, 4, 2, 3, 2, 5])

Answer 9

ПЛОХАЯ жадная эвристика для решения этой проблемы: попробуйте отсортировать список от наименьшего к наибольшему и разбить этот список на два, указав list1 = нечетные элементы и list2 = четные элементы.