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

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

Существует решение, включающее динамическое программирование, которое выполняется в O(n*TotalSum), где n - это количество элементов в массиве, а TotalSum - их общая сумма.

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

Для массива размером n мы назовем это T(n),

T(n) = T(n-1) UNION { Array[n]+k | k is in T(n-1) }

(Доказательство правильности - по индукции, как в большинстве случаев рекурсивных функций.)

Также запомните для каждой ячейки в динамической матрице элементы, которые были добавлены для ее создания.

Простой анализ сложности покажет, что это сделано в O(n*TotalSum).

После вычисления T(n) найдите в наборе элемент, размер которого точно равен TotalSum / 2.

Если такой элемент существует, то элементы, которые его создали, сложенные вместе, равны TotalSum / 2, а элементы, которые не были частью его создания, также равны TotalSum / 2 (TotalSum - TotalSum / 2 = TotalSum / 2).

Это псевдополиномиальное решение. AFAIK, эта проблема, как известно, не в P .

Answer 2

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

Answer 3

В обычном варианте эта проблема накладывает 2 ограничения, и это можно сделать более простым способом.

1. Если разбиение можно выполнить только где-то по длине массива (мы не делаемсчитать элементы не по порядку)
2. Нет отрицательных чисел.

В таком случае алгоритм может быть таким:

1. Имеет 2 переменные, leftSum иrightSum
2. Начните увеличивать leftSum слева и rightSum справа от массива.
3. Попробуйте исправить любой дисбаланс в нем.

Следующий код делаетвыше:

public boolean canBalance(int[] nums) {
  int leftSum = 0, rightSum = 0, i, j;
  if(nums.length == 1)
      return false;
  for(i=0, j=nums.length-1; i<=j ;){
      if(leftSum <= rightSum){
         leftSum+=nums[i];
         i++;
      }else{
         rightSum+=nums[j];
         j--;
      }
  }
  return (rightSum == leftSum);
}

Вывод:

canBalance({1, 1, 1, 2, 1})       → true    OK      
canBalance({2, 1, 1, 2, 1})       → false   OK      
canBalance({10, 10})              → true    OK          
canBalance({1, 1, 1, 1, 4})       → true    OK      
canBalance({2, 1, 1, 1, 4})       → false   OK      
canBalance({2, 3, 4, 1, 2})       → false   OK      
canBalance({1, 2, 3, 1, 0, 2, 3}) → true    OK      
canBalance({1, 2, 3, 1, 0, 1, 3}) → false   OK      
canBalance({1})                   → false   OK      
canBalance({1, 1, 1, 2, 1})       → true    OK

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

Answer 4

    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;   
}

Answer 5

Пожалуйста, попробуйте это и дайте мне знать, если не работает. Надеюсь, это поможет вам.

static ArrayList<Integer> array = null;

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

    ArrayList<Integer> inputArray = getinputArray();
    System.out.println("inputArray is " + inputArray);
    Collections.sort(inputArray);

    int totalSum = 0;

    Iterator<Integer> inputArrayIterator = inputArray.iterator();
    while (inputArrayIterator.hasNext()) {
        totalSum = totalSum + inputArrayIterator.next();
    }
    if (totalSum % 2 != 0) {
        System.out.println("Not Possible");
        return;
    }

    int leftSum = inputArray.get(0);
    int rightSum = inputArray.get(inputArray.size() - 1);

    int currentLeftIndex = 0;
    int currentRightIndex = inputArray.size() - 1;

    while (leftSum <= (totalSum / 2)) {
        if ((currentLeftIndex + 1 != currentRightIndex)
                && leftSum != (totalSum / 2)) {
            currentLeftIndex++;
            leftSum = leftSum + inputArray.get(currentLeftIndex);
        } else
            break;

    }
    if (leftSum == (totalSum / 2)) {
        ArrayList<Integer> splitleft = new ArrayList<Integer>();
        ArrayList<Integer> splitright = new ArrayList<Integer>();

        for (int i = 0; i <= currentLeftIndex; i++) {
            splitleft.add(inputArray.get(i));
        }
        for (int i = currentLeftIndex + 1; i < inputArray.size(); i++) {
            splitright.add(inputArray.get(i));
        }
        System.out.println("splitleft is :" + splitleft);
        System.out.println("splitright is :" + splitright);

    }

    else
        System.out.println("Not possible");
}

public static ArrayList<Integer> getinputArray() {
    Scanner scanner = new Scanner(System.in);
    array = new ArrayList<Integer>();
    int size;
    System.out.println("Enter the Initial array size : ");
    size = scanner.nextInt();
    System.out.println("Enter elements in the array");
    for (int j = 0; j < size; j++) {
        int element;
        element = scanner.nextInt();
        array.add(element);
    }
    return array;
}

}

Answer 6

Это рекурсивное решение проблемы, одно нерекурсивное решение могло бы использовать вспомогательный метод для получения суммы индексов 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);
}

Answer 7

Пробовал другое решение. кроме решений Wiki (проблема с разделами).

static void subSet(int array[]) {
    System.out.println("Input elements  :" + Arrays.toString(array));

    int sum = 0;
    for (int element : array) {
        sum = sum + element;
    }
    if (sum % 2 == 1) {
        System.out.println("Invalid Pair");
        return;
    }

    Arrays.sort(array);
    System.out.println("Sorted elements :" + Arrays.toString(array));

    int subSum = sum / 2;

    int[] subSet = new int[array.length];
    int tmpSum = 0;
    boolean isFastpath = true;
    int lastStopIndex = 0;
    for (int j = array.length - 1; j >= 0; j--) {
        tmpSum = tmpSum + array[j];
        if (tmpSum == subSum) { // if Match found
            if (isFastpath) { // if no skip required and straight forward
                                // method
                System.out.println("Found SubSets 0..." + (j - 1) + " and "
                        + j + "..." + (array.length - 1));
            } else {
                subSet[j] = array[j];
                array[j] = 0;
                System.out.println("Found..");
                System.out.println("Set 1" + Arrays.toString(subSet));
                System.out.println("Set 2" + Arrays.toString(array));
            }
            return;
        } else {
            // Either the tmpSum greater than subSum or less .
            // if less , just look for next item
            if (tmpSum < subSum && ((subSum - tmpSum) >= array[0])) {
                if (lastStopIndex > j && subSet[lastStopIndex] == 0) {
                    subSet[lastStopIndex] = array[lastStopIndex];
                    array[lastStopIndex] = 0;
                }
                lastStopIndex = j;
                continue;
            }
            isFastpath = false;
            if (subSet[lastStopIndex] == 0) {
                subSet[lastStopIndex] = array[lastStopIndex];
                array[lastStopIndex] = 0;
            }
            tmpSum = tmpSum - array[j];
        }
    }

}

Я проверял. (Хорошо работает с положительным числом больше 0), пожалуйста, дайте мне знать, если у вас есть какие-либо проблемы.

Answer 8

package PACKAGE1;

import java.io.*;
import java.util.Arrays;

public class programToSplitAnArray {

    public static void main(String args[]) throws NumberFormatException,
            IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("enter the no. of elements to enter");
        int n = Integer.parseInt(br.readLine());
        int x[] = new int[n];
        int half;
        for (int i = 0; i < n; i++) {

            x[i] = Integer.parseInt(br.readLine());
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum = sum + x[i];
        }
        if (sum % 2 != 0) {
            System.out.println("the sum is odd and cannot be divided");
            System.out.println("The sum is " + sum);
        }

        else {
            boolean div = false;
            half = sum / 2;
            int sum1 = 0;
            for (int i = 0; i < n; i++) {

                sum1 = sum1 + x[i];
                if (sum1 == half) {
                    System.out.println("array can be divided");
                    div = true;
                    break;
                }

            }
            if (div == true) {
                int t = 0;
                int[] array1 = new int[n];
                int count = 0;
                for (int i = 0; i < n; i++) {
                    t = t + x[i];
                    if (t <= half) {
                        array1[i] = x[i];
                        count++;
                    }
                }
                array1 = Arrays.copyOf(array1, count);
                int array2[] = new int[n - count];
                int k = 0;
                for (int i = count; i < n; i++) {
                    array2[k] = x[i];
                    k++;
                }
                System.out.println("The first array is ");
                for (int m : array1) {

                    System.out.println(m);
                }
                System.out.println("The second array is ");
                for (int m : array2) {

                    System.out.println(m);
                }
            } else {
                System.out.println("array cannot be divided");
            }
        }
    }

}

Answer 9

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

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

Answer 10

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

пакетное решение; 

 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); 

} }