How to optimally divide an array into two subarrays so that sum of elements in both are same, otherwise give an error?

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

    public boolean splitBetween(int[] x){
    int sum=0;
    int sum1=0;
    if (x.length==1){
        System.out.println("Not a valid value");
    }

    for (int i=0;i<x.length;i++){
        sum=sum+x[i];
        System.out.println(sum);
        for (int j=i+1;j<x.length;j++){
            sum1=sum1+x[j];
            System.out.println("SUm1:"+sum1);

        }

        if(sum==sum1){
            System.out.println("split possible");
            System.out.println("Sum: " +sum +" Sum1:" + sum1);
            return true;
        }else{
            System.out.println("Split not possible");
        }

        sum1=0;
    }
    return false;   
}

Это рекурсивное решение проблемы, одно нерекурсивное решение могло бы использовать вспомогательный метод для получения суммы индексов 0 к текущему индексу в цикле for, а другое могло бы получить сумму всех элементов из одного и того же текущий индекс до конца, который работает. Теперь, если вы хотите получить элементы в массив и сравнить сумму, сначала найдите точку (индекс), которая отмечает разлив, где сумма обеих сторон равна, затем возьмите список и добавьте значения перед этим индексом и еще один список для перехода. после этого индекса.

Вот мой (рекурсия), который только определяет, есть ли место для разбиения массива так, чтобы сумма чисел на одной стороне равнялась сумме чисел на другой стороне. Беспокойство по поводу indexOutOfBounds, которое может легко произойти в рекурсии, небольшая ошибка может оказаться фатальной и привести к множеству исключений и ошибок.

public boolean canBalance(int[] nums) {
  return (nums.length <= 1) ? false : canBalanceRecur(nums, 0);   
}
public boolean canBalanceRecur(int[] nums, int index){ //recursive version
  if(index == nums.length - 1 && recurSumBeforeIndex(nums, 0, index) 
  != sumAfterIndex(nums, index)){ //if we get here and its still bad
  return false;
  }
  if(recurSumBeforeIndex(nums, 0, index + 1) == sumAfterIndex(nums, index + 1)){
  return true;
  }
  return canBalanceRecur(nums, index + 1); //move the index up
}
public int recurSumBeforeIndex(int[] nums, int start, int index){
   return (start == index - 1 && start < nums.length) 
   ? nums[start] 
   : nums[start] + recurSumBeforeIndex(nums, start + 1, index);
}

public int sumAfterIndex(int[] nums, int startIndex){
  return (startIndex == nums.length - 1) 
  ? nums[nums.length - 1] 
  : nums[startIndex] + sumAfterIndex(nums, startIndex + 1);
}

Во-первых, если элементы являются целыми числами, проверьте, что сумма делится поровну на два - если это не удачно, невозможно.

Я бы поставил задачу в виде двоичного дерева, где уровень 0 решает, в какой элемент набора 0 входит, уровень 1 решает, в какой элемент набора 1 входит и т. Д. В любое время, если сумма одного набора равна половине всей Готово - успех. В любое время, если сумма одного набора составляет более половины общей суммы, это поддерево является ошибкой, и вам необходимо выполнить резервное копирование. В этот момент это проблема обхода дерева.

Задача @Gal Subset-Sum является NP-Complete и имеет алгоритм псевдополиномиального динамического программирования 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);
     }

}

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

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

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

https://github.com/ShubhamAgrahari/DRjj/blob/master/Subarray_Sum.java

package solution;

import java.util.Scanner;

public class Solution {

static int SplitPoint(int arr[], int n) 
{ 

 int leftSum = 0; 

for (int i = 0 ; i < n ; i++) 
    leftSum += arr[i]; 

int rightSum = 0; 

for (int i = n-1; i >= 0; i--) 
{ 

    rightSum += arr[i]; 


    leftSum -= arr[i] ; 

    if (rightSum == leftSum) 
        return i ; 
} 
         return -1; 
} 


static void output(int arr[], int n) 
{ 
    int s = SplitPoint(arr, n); 

    if (s == -1 || s == n ) 
    { 
        System.out.println("Not Possible" ); 
        return; 
    } 
    for (int i = 0; i < n; i++) 
    { 
        if(s == i) 
            System.out.println(); 

        System.out.print(arr[i] + " "); 
    } 
} 

   public static void main (String[] args) { 

  Scanner sc= new Scanner(System.in);

    System.out.println("Enter Array Size");
    int n = sc.nextInt();
    int arr[]= new int[n];
    for(int i=0;i<n;i++)
    {
        arr[i]=sc.nextInt();
    }
output(arr, n); 

} } 

    def listSegmentation(theList):
    newList = [[],[]]
    print(theList)

    wt1 = 0
    wt2 = 0
    dWt = 0

    for idx in range(len(theList)):
        wt = theList[idx]

        if (wt > (wt1 + wt2) and wt1 > 0 and wt2 > 0):
            newList[0] = newList[0] + newList[1]
            newList[1] = []
            newList[1].append(wt)
            wt1 += wt2
            wt2 = wt 
        elif ((wt2 + wt) >= (wt1 + wt)):
            wt1 += wt
            newList[0].append(wt)
        elif ((wt2 + wt) < (wt1 + wt)):
            wt2 += wt
            newList[1].append(wt)

    #Balancing
    if(wt1 > wt2):
        wtDiff = sum(newList[0]) - sum(newList[1])
        ls1 = list(filter(lambda x: x <= wtDiff, newList[0]))
        ls2 = list(filter(lambda x: x <= (wtDiff/2) , newList[1]))

        while len(ls1) > 0 or len(ls2) > 0:
            if len(ls1) > 0:
                elDif1 = max(ls1)
                newList[0].remove(elDif1)
                newList[1].append(elDif1)

            if len(ls2) > 0:
                elDif2 = max(ls2)
                newList[0].append(elDif2)
                newList[1].remove(elDif2)

            wtDiff = sum(newList[0]) - sum(newList[1])
            ls1 = list(filter(lambda x: x <= wtDiff, newList[0]))
            ls2 = list(filter(lambda x: x <= (wtDiff/2) , newList[1]))


    if(wt2 > wt1):
        wtDiff = sum(newList[1]) - sum(newList[0])
        ls2 = list(filter(lambda x: x <= wtDiff, newList[1]))
        ls1 = list(filter(lambda x: x <= (wtDiff/2) , newList[0]))
        while len(ls1) > 0 or len(ls2) > 0:
            if len(ls1) > 0:
                elDif1 = max(ls1)
                newList[0].remove(elDif1)
                newList[1].append(elDif1)

            if len(ls2) > 0:
                elDif2 = max(ls2)
                newList[0].append(elDif2)
                newList[1].remove(elDif2)

            wtDiff = sum(newList[1]) - sum(newList[0])
            ls2 = list(filter(lambda x: x <= wtDiff, newList[1]))
            ls1 = list(filter(lambda x: x <= (wtDiff/2) , newList[0]))
            print(ls1, ls2)


    print(sum(newList[0]),sum(newList[1]))
    return newList


#Test cases
lst1 = [4,9,8,3,11,6,13,7,2,25,28,60,19,196]
lst2 = [7,16,5,11,4,9,15,2,1,13]
lst3 = [8,17,14,9,3,5,19,11,4,6,2]

print(listSegmentation(lst1))
print(listSegmentation(lst2))
print(listSegmentation(lst3))