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

Ответ 1

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

}

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

Ответ 2

Существует решение, которое включает в себя динамическое программирование, которое выполняется в 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/2, а элементы, которые не были частью его создания, также равны TotalSum/2 (TotalSum - TotalSum/2 = TotalSum/2).

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

Ответ 3

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

Ответ 4

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

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

Алгоритм, который затем работает, может быть:

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

Следующий код делает следующее:

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

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

Ответ 5

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

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

Ответ 6

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

Предположим, что массив 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);

Ответ 7

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

}

Ответ 8

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

Ответ 9

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

Ответ 10

Ниже приведена рабочая версия кода в С#

static int flag;

void display(List<int> input, int numOfElements, List<int> solution, int index)
{
    Dictionary<int, int> map = new Dictionary<int, int>();

    for (int i = 0; i < numOfElements; i++)
    {
        if (map.ContainsKey(input[i]))
            map[input[i]] = map[input[i]] + 1;
        else
            map.Add(input[i], 1);
    }

    Console.WriteLine("First Subset ");

    for (int i = 0; i < index; i++)
    {
        Console.Write(solution[i] + " ");
        map[solution[i]] = map[solution[i]] - 1;
    }

    Console.WriteLine();

    Console.WriteLine("Second Subset ");

    foreach (var kv in map)
    {
        var value = kv.Value;

        while (value-- > 0)
            Console.Write(kv.Key + " ");
    }
}

// this function is implemented to find the set of elemtns that sum to required value and remaining array elements will already be another set
void subset(List<int> input, int numOfElements, List<int> solution, int sum, int i, int index)
{
    if (flag == 1) return;

    if (sum == 0)
    {
        display(input, numOfElements, solution, index);
        flag = 1;
        return;
    }

    if (sum < 0 || i > numOfElements - 1)
        return;

    subset(input, numOfElements, solution, sum, (i + 1), index);

    solution[index] = input[i];

    subset(input, numOfElements, solution, (sum - input[i]), i + 1, index + 1);
}

void Main()
{
    int totalSum = 0;

    List<int> input = new List<int> { 10, 20 , 30 , 5 , 40 , 50 , 40 , 15 };

    totalSum = input.Sum();

    if (totalSum % 2 == 1)
        Console.WriteLine("Not Possible");

    int sum = totalSum / 2;

    List<int> solution = new List<int>() { 0, 0, 0, 0, 0, 0, 0, 0 };

    flag = 0;

    subset(input, input.Count, solution, sum, 0, 0);

    if (flag == 0)
        Console.WriteLine("Not Possible");
}

Ответ 11

Нашел решение здесь

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

Ответ 12

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

Ответ 13

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

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

Ответ 14

Алгоритм:

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

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

Программа java доступна в Java Code

Ответ 15

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

}

Ответ 16

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

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

}

Ответ 17

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

Ответ 18

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

package solution; 

импорт java.util.Scanner;

Public Class Solution {

Ответ 19

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

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