Рубрики

Перетягивание каната

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

Например, пусть заданный набор равен {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, размер набора равен 10. Выход для этого набора должен быть {4, 100, 1, 23, 20} и {3, 5, -3, 89, 54}. Оба выходных подмножества имеют размер 5, и сумма элементов в обоих подмножествах одинакова (148 и 148).
Давайте рассмотрим другой пример, где n нечетно. Пусть заданным набором будет {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. Выходные подмножества должны быть {45, -34, 12, 98, -1} и {23, 0, -99, 4, 189, 4}. Суммы элементов в двух подмножествах равны 120 и 121 соответственно.

Следующее решение пробует все возможные подмножества половинного размера. Если сформировано одно подмножество половинного размера, остальные элементы образуют другое подмножество. Мы инициализируем текущий набор как пустой и строим его один за другим. Для каждого элемента есть две возможности: либо он является частью текущего набора, либо является частью остальных элементов (другого подмножества). Мы рассматриваем обе возможности для каждого элемента. Когда размер текущего набора становится n / 2, мы проверяем, является ли это решение лучшим, чем лучшее из доступных на данный момент. Если это так, то мы обновляем лучшее решение.

Ниже приводится реализация проблемы перетягивания каната. Он печатает необходимые массивы.

C ++

#include <iostream>
#include <stdlib.h>
#include <limits.h>

using namespace std;

  
// функция, которая пробует каждое возможное решение, вызывая себя рекурсивно

void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements,

             bool* soln, int* min_diff, int sum, int curr_sum, int curr_position)

{

    // проверяет, выходит ли оно за пределы

    if (curr_position == n)

        return;

  

    // проверяет, что количество оставшихся элементов не меньше

    // количество элементов, необходимых для формирования решения

    if ((n/2 - no_of_selected_elements) > (n - curr_position))

        return;

  

    // рассмотрим случаи, когда текущий элемент не включен в решение

    TOWUtil(arr, n, curr_elements, no_of_selected_elements,

              soln, min_diff, sum, curr_sum, curr_position+1);

  

    // добавляем текущий элемент в решение

    no_of_selected_elements++;

    curr_sum = curr_sum + arr[curr_position];

    curr_elements[curr_position] = true;

  

    // проверяет, сформировано ли решение

    if (no_of_selected_elements == n/2)

    {

        // проверяет, является ли сформированное решение лучше, чем лучшее решение

        if (abs(sum/2 - curr_sum) < *min_diff)

        {

            *min_diff = abs(sum/2 - curr_sum);

            for (int i = 0; i<n; i++)

                soln[i] = curr_elements[i];

        }

    }

    else

    {

        // рассмотрим случаи, когда текущий элемент включен в решение

        TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln,

                  min_diff, sum, curr_sum, curr_position+1);

    }

  

    // удаляет текущий элемент перед возвратом к вызывающей функции

    curr_elements[curr_position] = false;

}

  
// основная функция, которая генерирует обр

void tugOfWar(int *arr, int n)

{

    // логический массив, который содержит включение и исключение элемента

    // в текущем наборе. Номер, исключенный автоматически из другого набора

    bool* curr_elements = new bool[n];

  

    // Массив включения / исключения для окончательного решения

    bool* soln = new bool[n];

  

    int min_diff = INT_MAX;

  

    int sum = 0;

    for (int i=0; i<n; i++)

    {

        sum += arr[i];

        curr_elements[i] =  soln[i] = false;

    }

  

    // Найти решение с помощью рекурсивной функции TOWUtil ()

    TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0);

  

    // Распечатать решение

    cout << "The first subset is: ";

    for (int i=0; i<n; i++)

    {

        if (soln[i] == true)

            cout << arr[i] << " ";

    }

    cout << "\nThe second subset is: ";

    for (int i=0; i<n; i++)

    {

        if (soln[i] == false)

            cout << arr[i] << " ";

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};

    int n = sizeof(arr)/sizeof(arr[0]);

    tugOfWar(arr, n);

    return 0;

}

Джава

// Java программа для перетягивания каната

import java.util.*;

import java.lang.*;

import java.io.*;

  

class TugOfWar

{

    public int min_diff;

      

    // функция, которая пробует каждое возможное решение

    // вызывая себя рекурсивно

    void TOWUtil(int arr[], int n, boolean curr_elements[],

               int no_of_selected_elements, boolean soln[],

               int sum, int curr_sum, int curr_position)

    {

        // проверяет, выходит ли оно за пределы

        if (curr_position == n)

            return;

  

        // проверяет, осталось ли количество элементов

        // не меньше количества элементов

        // требуется для формирования решения

        if ((n / 2 - no_of_selected_elements) >

                (n - curr_position))

            return;

  

        // рассмотрим случаи, когда текущий элемент

        // не входит в решение

        TOWUtil(arr, n, curr_elements, 

               no_of_selected_elements, soln, sum,

               curr_sum, curr_position+1);

  

        // добавляем текущий элемент в решение

        no_of_selected_elements++;

        curr_sum = curr_sum + arr[curr_position];

        curr_elements[curr_position] = true;

  

        // проверяет, сформировано ли решение

        if (no_of_selected_elements == n / 2)

        {

            // проверяет, является ли сформированное решение

            // лучше, чем лучшее решение, так

            // далеко

            if (Math.abs(sum / 2 - curr_sum) <

                                  min_diff)

            {

                min_diff = Math.abs(sum / 2 -

                                  curr_sum);

                for (int i = 0; i < n; i++)

                    soln[i] = curr_elements[i];

            }

        }

        else

        {

            // рассмотрим случаи, когда текущие

            // элемент включен в

            // решение

            TOWUtil(arr, n, curr_elements, 

                    no_of_selected_elements, 

                    soln, sum, curr_sum, 

                    curr_position + 1);

        }

  

        // удаляет текущий элемент перед

        // возвращаясь к вызывающему

        // функция

        curr_elements[curr_position] = false;

    }

  

    // основная функция, которая генерирует обр

    void tugOfWar(int arr[])

    {

        int n = arr.length; 

  

        // логический массив, который содержит

        // включение и исключение элемента

        // в текущем наборе. Количество исключено

        // автоматически формируем другой набор

        boolean[] curr_elements = new boolean[n];

          

        // Массив включения / исключения для

        // окончательное решение

        boolean[] soln = new boolean[n];

  

        min_diff = Integer.MAX_VALUE;

  

        int sum = 0;

        for (int i = 0; i < n; i++)

        {

            sum += arr[i];

            curr_elements[i] = soln[i] = false;

        }

  

        // Найти решение используя рекурсив

        // функция TOWUtil ()

        TOWUtil(arr, n, curr_elements, 0

                soln, sum, 0, 0);

  

        // Распечатать решение

        System.out.print("The first subset is: ");

        for (int i = 0; i < n; i++)

        {

            if (soln[i] == true)

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

        }

        System.out.print("\nThe second subset is: ");

        for (int i = 0; i < n; i++)

        {

            if (soln[i] == false)

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

        }

    }

      

    // Программа драйвера для проверки вышеуказанных функций

    public static void main (String[] args) 

    {

        int arr[] = {23, 45, -34, 12, 0, 98,

                     -99, 4, 189, -1, 4};

        TugOfWar a = new TugOfWar();

        a.tugOfWar(arr);

    }

}

  
// Этот код предоставлен Чхави

python3

# Python3 программа для вышеуказанного подхода

  
# функция, которая пробует все возможное
# решение путем рекурсивного вызова самого себя

def TOWUtil(arr, n, curr_elements, no_of_selected_elements, 

            soln, min_diff, Sum, curr_sum, curr_position):

      

    # проверяет, идет ли

    # вне границы

    if (curr_position == n): 

        return

  

    # проверяет, что номера элементов

    # осталось не меньше количества

    # элементы, необходимые для формирования решения

    if ((int(n / 2) - no_of_selected_elements) > 

                          (n - curr_position)):

        return

  

    # рассмотрим случаи, когда текущий элемент

    # не входит в решение

    TOWUtil(arr, n, curr_elements, no_of_selected_elements, 

            soln, min_diff, Sum, curr_sum, curr_position + 1

  

    # добавить текущий элемент в решение

    no_of_selected_elements += 1

    curr_sum = curr_sum + arr[curr_position] 

    curr_elements[curr_position] = True

  

    # проверяет, сформировано ли решение

    if (no_of_selected_elements == int(n / 2)):

          

        # проверяет, является ли сформированное решение лучше

        # чем лучшее решение на данный момент

        if (abs(int(Sum / 2) - curr_sum) < min_diff[0]):

            min_diff[0] = abs(int(Sum / 2) - curr_sum)

            for i in range(n):

                soln[i] = curr_elements[i]

    else:

          

        # рассмотрим случаи, когда текущие

        # элемент включен в решение

        TOWUtil(arr, n, curr_elements, no_of_selected_elements, 

                soln, min_diff, Sum, curr_sum, curr_position + 1)

  

    # удаляет текущий элемент перед возвратом

    # к вызывающей стороне этой функции

    curr_elements[curr_position] = False

  
# основная функция, которая генерирует обр

def tugOfWar(arr, n):

      

    # логический массив, который содержит

    # включение и исключение элемента

    # в текущем наборе. Количество исключено

    # автоматически формирует другой набор

    curr_elements = [None] *

  

    # Массив включения / исключения

    # для окончательного решения

    soln = [None] *

  

    min_diff = [999999999999

  

    Sum = 0

    for i in range(n):

        Sum += arr[i] 

        curr_elements[i] = soln[i] = False

  

    # Найти решение с помощью рекурсии

    # function TOWUtil ()

    TOWUtil(arr, n, curr_elements, 0

            soln, min_diff, Sum, 0, 0

  

    # Распечатать решение

    print("The first subset is: ")

    for i in range(n):

        if (soln[i] == True):

            print(arr[i], end = " ")

    print()

    print("The second subset is: ")

    for i in range(n):

        if (soln[i] == False):

            print(arr[i], end = " ")

  
Код водителя

if __name__ == '__main__':

  

    arr = [23, 45, -34, 12, 0, 98

               -99, 4, 189, -1, 4

    n = len(arr) 

    tugOfWar(arr, n)

  
# Этот код предоставлен PranchalK

C #

// C # программа для перетягивания каната

using System;

  

class GFG 

    public int min_diff; 

      

    // функция, которая пробует каждое возможное решение

    // вызывая себя рекурсивно

    void TOWUtil(int []arr, int n, Boolean []curr_elements, 

                 int no_of_selected_elements, Boolean []soln, 

                 int sum, int curr_sum, int curr_position) 

    

        // проверяет, выходит ли оно за пределы

        if (curr_position == n) 

            return

  

        // проверяет, осталось ли количество элементов

        // не меньше количества элементов

        // требуется для формирования решения

        if ((n / 2 - no_of_selected_elements) > 

            (n - curr_position)) 

            return

  

        // рассмотрим случаи, когда текущий элемент

        // не входит в решение

        TOWUtil(arr, n, curr_elements, 

                no_of_selected_elements, soln, sum,

                curr_sum, curr_position + 1); 

  

        // добавляем текущий элемент в решение

        no_of_selected_elements++; 

        curr_sum = curr_sum + arr[curr_position]; 

        curr_elements[curr_position] = true

  

        // проверяет, сформировано ли решение

        if (no_of_selected_elements == n / 2) 

        

            // проверяет, является ли сформированное решение

            // лучше, чем лучшее решение, так

            // далеко

            if (Math.Abs(sum / 2 - curr_sum) < 

                                   min_diff) 

            

                min_diff = Math.Abs(sum / 2 - 

                                    curr_sum); 

                for (int i = 0; i < n; i++) 

                    soln[i] = curr_elements[i]; 

            

        

        else

        

            // рассмотрим случаи, когда текущие

            // элемент включен в

            // решение

            TOWUtil(arr, n, curr_elements, 

                    no_of_selected_elements, 

                    soln, sum, curr_sum, 

                    curr_position + 1); 

        

  

        // удаляет текущий элемент перед

        // возвращаясь к вызывающему

        // функция

        curr_elements[curr_position] = false

    

  

    // основная функция, которая генерирует обр

    void tugOfWar(int []arr) 

    

        int n = arr.Length; 

  

        // логический массив, который содержит

        // включение и исключение элемента

        // в текущем наборе. Количество исключено

        // автоматически формируем другой набор

        Boolean[] curr_elements = new Boolean[n]; 

          

        // Массив включения / исключения для

        // окончательное решение

        Boolean[] soln = new Boolean[n]; 

  

        min_diff = int.MaxValue; 

  

        int sum = 0; 

        for (int i = 0; i < n; i++) 

        

            sum += arr[i]; 

            curr_elements[i] = soln[i] = false

        

  

        // Найти решение используя рекурсив

        // функция TOWUtil ()

        TOWUtil(arr, n, curr_elements, 0, 

                soln, sum, 0, 0); 

  

        // Распечатать решение

        Console.Write("The first subset is: "); 

        for (int i = 0; i < n; i++) 

        

            if (soln[i] == true

                Console.Write(arr[i] + " "); 

        

        Console.Write("\nThe second subset is: "); 

        for (int i = 0; i < n; i++) 

        

            if (soln[i] == false

                Console.Write(arr[i] + " "); 

        

    

      

    // Код драйвера

    public static void Main (String[] args) 

    

        int []arr = {23, 45, -34, 12, 0, 98, 

                    -99, 4, 189, -1, 4}; 

        GFG a = new GFG(); 

        a.tugOfWar(arr); 

    

  
// Этот код предоставлен 29AjayKumar

PHP

<?php
// PHP программа для вышеуказанного подхода

  
// Функция, которая пробует все возможное
// решение путем рекурсивного вызова самого себя

function TOWUtil(&$arr, $n, &$curr_elements

                  $no_of_selected_elements

                 &$soln, &$min_diff, $sum

                  $curr_sum, $curr_position

    // проверяет, идет ли

    // вне границы

    if ($curr_position == $n

        return

  

    // проверяет, осталось ли количество элементов

    // не меньше количества элементов

    // требуется для формирования решения

    if ((intval($n / 2) - $no_of_selected_elements) > 

                             ($n - $curr_position)) 

        return

  

    // рассмотрим случаи, когда текущий элемент

    // не входит в решение

    TOWUtil($arr, $n, $curr_elements

            $no_of_selected_elements

            $soln, $min_diff, $sum

            $curr_sum, $curr_position + 1); 

  

    // добавляем текущий элемент в решение

    $no_of_selected_elements++; 

    $curr_sum = ($curr_sum +

                 $arr[$curr_position]); 

    $curr_elements[$curr_position] = true; 

  

    // проверяет, сформировано ли решение

    if ($no_of_selected_elements == intval($n / 2)) 

    

        // проверяет, является ли сформированное решение

        // лучше, чем лучшее решение

        if (abs(intval($sum / 2) - 

                       $curr_sum) < $min_diff

        

            $min_diff = abs(intval($sum / 2) - 

                                   $curr_sum); 

            for ($i = 0; $i < $n; $i++) 

                $soln[$i] = $curr_elements[$i]; 

        

    

    else

    

        // рассмотрим случаи, когда текущие

        // элемент включен в решение

        TOWUtil($arr, $n, $curr_elements

                $no_of_selected_elements, $soln

                $min_diff, $sum, $curr_sum

                $curr_position + 1); 

    

  

    // удаляет текущий элемент перед

    // возвращаемся к вызывающей стороне этой функции

    $curr_elements[$curr_position] = false; 

  
// основная функция, которая генерирует обр

function tugOfWar(&$arr, $n

    // логический массив, который содержит

    // включение и исключение элемента

    // в текущем наборе. Количество исключено

    // автоматически формируем другой набор

    $curr_elements = array_fill(0, $n, 0);

  

    // Массив включения / исключения

    // для окончательного решения

    $soln = array_fill(0, $n, 0);

  

    $min_diff = PHP_INT_MAX; 

  

    $sum = 0; 

    for ($i = 0; $i < $n; $i++) 

    

        $sum += $arr[$i]; 

        $curr_elements[$i] = $soln[$i] = false; 

    

  

    // Найти решение используя рекурсив

    // функция TOWUtil ()

    TOWUtil($arr, $n, $curr_elements, 0,

            $soln, $min_diff, $sum, 0, 0); 

  

    // Распечатать решение

    echo "The first subset is: "

    for ($i = 0; $i < $n; $i++) 

    

        if ($soln[$i] == true) 

            echo $arr[$i] . " "

    

    echo "\nThe second subset is: "

    for ($i = 0; $i < $n; $i++) 

    

        if ($soln[$i] == false) 

            echo $arr[$i] . " "

    

  
// Код драйвера

$arr = array(23, 45, -34, 12, 0, 98,

            -99, 4, 189, -1, 4); 

$n = count($arr); 

tugOfWar($arr, $n); 

  
// Этот код добавлен
// ратбхупендра
?>


Выход:

The first subset is: 45 -34 12 98 -1
The second subset is: 23 0 -99 4 189 4

Эта статья составлена Ашишем Анандом и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Перетягивание каната

0.00 (0%) 0 votes