Рубрики

Минимизируйте денежный поток среди данного набора друзей, которые одолжили деньги друг у друга

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

Пример:
На следующей диаграмме показаны входные долги, подлежащие погашению.

Вышеупомянутые долги могут быть урегулированы следующим оптимизированным способом

Идея состоит в том, чтобы использовать алгоритм Жадности, где на каждом этапе рассчитывают все суммы одного человека и повторяют для оставшихся n-1 человек.
Как выбрать первого человека? Чтобы выбрать первого человека, рассчитайте чистую сумму для каждого человека, у которого получена чистая сумма, вычитая все долги (суммы к уплате) из всех кредитов (суммы к уплате). После оценки чистой суммы на каждого человека найдите двух человек с максимальной и минимальной чистой суммой. Эти два человека являются наиболее кредиторами и должниками. Человек с минимум двумя — наш первый человек, который будет рассмотрен и удален из списка. Пусть минимум двух сумм будет х. Мы выплачиваем сумму х от максимального должника максимальному кредитору и рассчитываем одного человека. Если х равен максимальному дебету, то рассчитывается максимальный дебитор, в противном случае рассчитывается максимальный кредитор.

Ниже приведен подробный алгоритм.

Делайте следующее для каждого человека Pi, где я от 0 до n-1.
1) Рассчитать сумму нетто для каждого человека. Чистая сумма для лица «i» может быть рассчитана путем вычитания суммы всех долгов из суммы всех кредитов.

2) Найдите двух человек, которые являются максимальным кредитором и максимальным должником. Пусть максимальная сумма для зачисления максимальный кредитор будет maxCredit, а максимальная сумма для зачисления от максимального должника будет maxDebit. Пусть максимальный должник будет Pd, а максимальный кредитор — Pc.

3) Найти минимум maxDebit и maxCredit. Пусть минимум два будет х. Дебет х из Pd и зачислить эту сумму в Pc

4) Если x равно maxCredit, то удалите Pc из набора лиц и повторите для остальных (n-1) человек.

5)
Если x равен maxDebit, то удалите Pd из набора лиц и повторите для остальных (n-1) человек.

Спасибо Balaji S за предложение этого метода в комментарии здесь .

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для поиска максимального денежного потока среди множества людей
#include<iostream>

using namespace std;

  
// Количество человек (или вершин в графе)
#define N 3

  
// Вспомогательная функция, которая возвращает индекс минимального значения в arr []

int getMin(int arr[])

{

    int minInd = 0;

    for (int i=1; i<N; i++)

        if (arr[i] < arr[minInd])

            minInd = i;

    return minInd;

}

  
// Вспомогательная функция, которая возвращает индекс максимального значения в arr []

int getMax(int arr[])

{

    int maxInd = 0;

    for (int i=1; i<N; i++)

        if (arr[i] > arr[maxInd])

            maxInd = i;

    return maxInd;

}

  
// Функция полезности, которая возвращает минимум 2 значения

int minOf2(int x, int y)

{

    return (x<y)? x: y;

}

  
// сумма [p] указывает чистую сумму для зачисления / списания
// к / от человека 'p'
// Если сумма [p] положительна, то i'th person будет равна [i]
// Если сумма [p] отрицательна, то i'th person выдаст -amount [i]

void minCashFlowRec(int amount[])

{

    // Находим индексы минимальных и максимальных значений в количестве []

    // сумма [mxCredit] указывает максимальную сумму, которая будет предоставлена

    // (или зачислено) любому человеку.

    // И количество [mxDebit] указывает максимальную сумму, которая будет взята

    // (или списано) с любого человека.

    // То есть, если есть положительное значение в количество [], то должен

    // быть отрицательным значением

    int mxCredit = getMax(amount), mxDebit = getMin(amount);

  

    // Если обе суммы равны 0, то все суммы рассчитываются

    if (amount[mxCredit] == 0 && amount[mxDebit] == 0)

        return;

  

    // Находим минимум двух сумм

    int min = minOf2(-amount[mxDebit], amount[mxCredit]);

    amount[mxCredit] -= min;

    amount[mxDebit] += min;

  

    // Если минимальная максимальная сумма

    cout << "Person " << mxDebit << " pays " << min

         << " to " << "Person " << mxCredit << endl;

  

    // Повторение для массива количества. Обратите внимание, что гарантируется, что

    // рекурсия прекратится как любая сумма [mxCredit]

    // или сумма [mxDebit] становится 0

    minCashFlowRec(amount);

}

  
// Задано множество людей в виде графа [], где граф [i] [j] указывает
// сумма, которую я должен заплатить человеку j, эта функция
// находит и печатает минимальный денежный поток для погашения всех долгов.

void minCashFlow(int graph[][N])

{

    // Создаем количество массива [], инициализируем все значения в нем как 0.

    int amount[N] = {0};

  

    // Рассчитаем сумму нетто, подлежащую выплате человеку 'p', и

    // сохраняет его в количестве [p]. Значение суммы [p] может быть

    // рассчитывается путем вычитания долгов 'p' из кредитов 'p'

    for (int p=0; p<N; p++)

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

          amount[p] += (graph[i][p] -  graph[p][i]);

  

    minCashFlowRec(amount);

}

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

int main()

{

    // graph [i] [j] указывает сумму, которая нужна мне

    // платное лицо j

    int graph[N][N] = { {0, 1000, 2000},

                        {0, 0, 5000},

                        {0, 0, 0},};

  

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

    minCashFlow(graph);

    return 0;

}

Джава

// Java-программа, чтобы найти максимум денег
// поток среди множества людей

  

class GFG

{

    // Количество человек (или вершин в графе)

    static final int N = 3;

      

    // Вспомогательная функция, которая возвращает

    // индекс минимального значения в arr []

    static int getMin(int arr[])

    {

        int minInd = 0;

        for (int i = 1; i < N; i++)

            if (arr[i] < arr[minInd])

                minInd = i;

        return minInd;

    }

      

    // Вспомогательная функция, которая возвращает

    // индекс максимального значения в arr []

    static int getMax(int arr[])

    {

        int maxInd = 0;

        for (int i = 1; i < N; i++)

            if (arr[i] > arr[maxInd])

                maxInd = i;

        return maxInd;

    }

      

    // Функция полезности, которая возвращает минимум 2 значения

    static int minOf2(int x, int y)

    {

        return (x < y) ? x: y;

    }

      

    // сумма [p] указывает чистую сумму

    // быть зачисленным / списанным с / от лица 'p'

    // Если сумма [p] положительна, то

    // i'th person будет составлять [i]

    // Если сумма [p] отрицательна, то

    // i'th человек выдаст -amount [i]

    static void minCashFlowRec(int amount[])

    {

        // Находим индексы минимума и

        // максимальные значения в количестве []

        // сумма [mxCredit] указывает максимальную сумму

        // быть переданным (или зачисленным) любому человеку.

        // И сумма [mxDebit] указывает максимальную сумму

        // быть взятым (или списанным) с любого человека.

        // Так что, если есть положительное значение в amount [],

        // тогда должно быть отрицательное значение

        int mxCredit = getMax(amount), mxDebit = getMin(amount);

      

        // Если обе суммы равны 0, то

        // все суммы рассчитаны

        if (amount[mxCredit] == 0 && amount[mxDebit] == 0)

            return;

      

        // Находим минимум двух сумм

        int min = minOf2(-amount[mxDebit], amount[mxCredit]);

        amount[mxCredit] -= min;

        amount[mxDebit] += min;

      

        // Если минимальная максимальная сумма

        System.out.println("Person " + mxDebit + " pays " + min

                                + " to " + "Person " + mxCredit);

      

        // Повторение для массива количества.

        // Обратите внимание, что гарантируется, что

        // рекурсия прекратится

        // как сумма [mxCredit] или

        // сумма [mxDebit] становится 0

        minCashFlowRec(amount);

    }

      

    // Задано множество людей в виде графа []

    // где graph [i] [j] указывает

    // сумма, которая нужна мне

    // платим человеку j, эта функция

    // находит и печатает минимум

    // денежный поток для погашения всех долгов.

    static void minCashFlow(int graph[][])

    {

        // Создать массив массива [],

        // инициализируем все значения в нем как 0.

        int amount[]=new int[N];

      

        // Рассчитаем сумму нетто

        // быть заплаченным человеку 'p', и

        // сохраняет его в количестве [p].

        // значение количества [p] может быть

        // рассчитывается путем вычитания

        // долги 'p' из кредитов 'p'

        for (int p = 0; p < N; p++)

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

            amount[p] += (graph[i][p] - graph[p][i]);

      

        minCashFlowRec(amount);

    }

      

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

    public static void main (String[] args)

    {

        // график [i] [j] указывает сумму

        // тот человек, которому я должен заплатить человеку j

        int graph[][] = { {0, 1000, 2000},

                            {0, 0, 5000},

                            {0, 0, 0},};

      

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

        minCashFlow(graph);

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для поиска максимума
# денежный поток среди множества лиц

  
Количество человек (или вершин в графе)

N = 3

  
# Сервисная функция, которая возвращает
# индекс минимального значения в arr []

def getMin(arr):

      

    minInd = 0

    for i in range(1, N):

        if (arr[i] < arr[minInd]):

            minInd = i

    return minInd

  
# Сервисная функция, которая возвращает
# индекс максимального значения в arr []

def getMax(arr):

  

    maxInd = 0

    for i in range(1, N):

        if (arr[i] > arr[maxInd]):

            maxInd = i

    return maxInd

  
# Полезная функция для
# вернуть минимум 2 значения

def minOf2(x, y):

  

    return x if x < y else y

  
# сумма [p] указывает сумму нетто
# быть зачисленным / списанным с / от человека 'p'
# Если сумма [р] положительна, то я
Количество человек будет [я]
# Если сумма [р] отрицательна, то я
# человек даст -счет [я]

def minCashFlowRec(amount):

  

    # Найти индексы минимума

    # и максимальные значения в количестве []

    # сумма [mxCredit] указывает на максимум

    # сумма, которая будет передана (или зачислена) любому лицу.

    # И количество [mxDebit] указывает максимальную сумму

    # быть взятым (или списанным) с любого человека.

    # Так что, если есть положительное значение в количестве [],

    # тогда должно быть отрицательное значение

    mxCredit = getMax(amount)

    mxDebit = getMin(amount)

  

    # Если обе суммы равны 0,

    # тогда все суммы рассчитываются

    if (amount[mxCredit] == 0 and amount[mxDebit] == 0):

        return 0

  

    # Найти минимум двух сумм

    min = minOf2(-amount[mxDebit], amount[mxCredit])

    amount[mxCredit] -=min

    amount[mxDebit] += min

  

    # Если минимальная максимальная сумма

    print("Person " , mxDebit , " pays " , min

        , " to " , "Person " , mxCredit)

  

    # Повтор для массива количества. Обратите внимание, что

    # гарантируется, что рекурсия

    # будет прерван как любая сумма [mxCredit]

    # или сумма [mxDebit] становится 0

    minCashFlowRec(amount)

  
# Заданный набор людей в виде графа [], где
# graph [i] [j] указывает количество, которое
человек, которому нужно заплатить человеку, это
# функция находит и печатает минимум
# денежный поток для погашения всех долгов.

def minCashFlow(graph):

  

    # Создать массив массива [],

    # инициализировать все значения в нем как 0.

    amount = [0 for i in range(N)]

  

    # Рассчитать сумму к оплате

    # человеку 'p' и сохраняет его в количестве [p].

    # Значение суммы [p] можно рассчитать по

    # вычитая долги 'p' из кредитов 'p'

    for p in range(N):

        for i in range(N):

            amount[p] += (graph[i][p] - graph[p][i])

  

    minCashFlowRec(amount)

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

  
# graph [i] [j] указывает сумму
# тот человек, которому я должен заплатить человеку j

graph = [ [0, 1000, 2000],

          [0, 0, 5000],

          [0, 0, 0] ]

  
minCashFlow(graph)

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для поиска максимальных денежных средств
// поток среди множества людей

using System;

  

class GFG

{

    // Количество человек (или

    // вершины в графе)

    static int N = 3;

      

    // Вспомогательная функция, которая возвращает

    // индекс минимального значения в arr []

    static int getMin(int []arr)

    {

        int minInd = 0;

        for (int i = 1; i < N; i++)

            if (arr[i] < arr[minInd])

                minInd = i;

        return minInd;

    }

      

    // Вспомогательная функция, которая возвращает

    // индекс максимального значения в arr []

    static int getMax(int []arr)

    {

        int maxInd = 0;

        for (int i = 1; i < N; i++)

            if (arr[i] > arr[maxInd])

                maxInd = i;

        return maxInd;

    }

      

    // Полезная функция для возврата

    // минимум 2 значения

    static int minOf2(int x, int y)

    {

        return (x < y) ? x: y;

    }

      

    // сумма [p] указывает чистую сумму

    // быть зачисленным / списанным с / от лица 'p'

    // Если сумма [p] положительна, то

    // i'th person будет составлять [i]

    // Если сумма [p] отрицательна, то

    // i'th человек выдаст -amount [i]

    static void minCashFlowRec(int []amount)

    {

        // Находим индексы минимума и

        // максимальные значения в количестве []

        // сумма [mxCredit] указывает максимальную сумму

        // быть переданным (или зачисленным) любому человеку.

        // И сумма [mxDebit] указывает максимальную сумму

        // быть взятым (или списанным) с любого человека.

        // Так что, если есть положительное значение в amount [],

        // тогда должно быть отрицательное значение

        int mxCredit = getMax(amount), mxDebit = getMin(amount);

      

        // Если обе суммы равны 0, то

        // все суммы рассчитаны

        if (amount[mxCredit] == 0 && 

            amount[mxDebit] == 0)

            return;

      

        // Находим минимум двух сумм

        int min = minOf2(-amount[mxDebit], amount[mxCredit]);

        amount[mxCredit] -= min;

        amount[mxDebit] += min;

      

        // Если минимальная максимальная сумма

        Console.WriteLine("Person " + mxDebit + 

                          " pays " + min + " to "

                          "Person " + mxCredit);

      

        // Повторение для массива количества.

        // Обратите внимание, что гарантируется, что

        // рекурсия прекратится

        // как сумма [mxCredit] или

        // сумма [mxDebit] становится 0

        minCashFlowRec(amount);

    }

      

    // Задано множество людей в виде графа []

    // где graph [i] [j] указывает

    // сумма, которая нужна мне

    // платим человеку j, эта функция

    // находит и печатает минимум

    // денежный поток для погашения всех долгов.

    static void minCashFlow(int [,]graph)

    {

        // Создать массив массива [],

        // инициализируем все значения в нем как 0.

        int []amount=new int[N];

      

        // Рассчитаем сумму нетто

        // быть заплаченным человеку 'p', и

        // сохраняет его в количестве [p].

        // значение количества [p] может быть

        // рассчитывается путем вычитания

        // долги 'p' из кредитов 'p'

        for (int p = 0; p < N; p++)

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

            amount[p] += (graph[i,p] - graph[p,i]);

      

        minCashFlowRec(amount);

    }

      

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

    public static void Main ()

    {

        // график [i] [j] указывает сумму

        // тот человек, которому я должен заплатить человеку j

        int [,]graph = { {0, 1000, 2000},

                         {0, 0, 5000},

                         {0, 0, 0},};

      

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

        minCashFlow(graph);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа, чтобы найти максимум наличных
// поток среди множества людей

  
// Количество человек (или вершин в графе)

$N = 3;

  
// Вспомогательная функция, которая возвращает
// индекс минимального значения в arr []

function getMin($arr)

{

    global $N;

    $minInd = 0;

    for ($i = 1; $i < $N; $i++)

        if ($arr[$i] < $arr[$minInd])

            $minInd = $i;

    return $minInd;

}

  
// Вспомогательная функция, которая возвращает
// индекс максимального значения в arr []

function getMax($arr)

{

    global $N;

    $maxInd = 0;

    for ($i = 1; $i < $N; $i++)

        if ($arr[$i] > $arr[$maxInd])

            $maxInd = $i;

    return $maxInd;

}

  
// Функция полезности, которая возвращает минимум 2 значения

function minOf2($x, $y)

{

    return ($x < $y)? $x: $y;

}

  
// сумма [p] указывает чистую сумму
// быть зачисленным / списанным с / от лица 'p'
// Если количество [р] положительное, то я
// человек будет [я]
// Если количество [р] отрицательно, то я
// человек даст -amount [i]

function minCashFlowRec($amount)

{

    // Находим индексы минимума и

    // максимальные значения в количестве []

    // сумма [mxCredit] указывает на

    // максимальная сумма, которую нужно дать

    // (или зачислено) любому человеку.

    // И количество [mxDebit] указывает на

    // максимальная сумма, которую нужно взять

    // (или списано) с любого человека.

    // Так что если есть положительное значение в

    // количество [], тогда должно

    // быть отрицательным значением

    $mxCredit = getMax($amount);

    $mxDebit = getMin($amount);

  

    // Если обе суммы равны 0, то

    // все суммы рассчитаны

    if ($amount[$mxCredit] == 0 && 

        $amount[$mxDebit] == 0)

        return;

  

    // Находим минимум двух сумм

    $min = minOf2(-$amount[$mxDebit], $amount[$mxCredit]);

    $amount[$mxCredit] -= $min;

    $amount[$mxDebit] += $min;

  

    // Если минимальная максимальная сумма

    echo "Person ".$mxDebit." pays ".$min." to Person ".$mxCredit."\n";

  

    // Повторение для массива количества. Заметка

    // что гарантировано, что

    // рекурсия прекратится как

    // любая сумма [mxCredit]

    // или сумма [mxDebit] становится 0

    minCashFlowRec($amount);

}

  
// Задано множество людей в виде графа []
// где graph [i] [j] обозначает
// количество человек, в которых я нуждаюсь
// платите человеку j, эта функция находит
// и печатает минимальный денежный поток
// для урегулирования всех долгов.

function minCashFlow($graph)

{

    global $N;

      

    // Создать массив массива [],

    // инициализируем все значения в нем как 0.

    $amount=array_fill(0, $N, 0);

  

    // Рассчитаем сумму нетто

    // выплачено человеку 'p', и магазины

    // это в количестве [p]. Значение

    // сумма [p] может быть рассчитана как

    // вычитаем долги 'p' из

    // кредиты 'p'

    for ($p = 0; $p < $N; $p++)

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

            $amount[$p] += ($graph[$i][$p] - $graph[$p][$i]);

  

    minCashFlowRec($amount);

}

  

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

  

    // график [i] [j] указывает сумму

    // тот человек, которому я должен заплатить человеку j

    $graph = array(array(0, 1000, 2000),

                        array(0, 0, 5000),

                        array(0, 0, 0));

  

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

    minCashFlow($graph);

      
// Этот код предоставлен mits
?>


Выход:

Person 1 pays 4000 to Person 2
Person 0 pays 3000 to Person 2

Алгоритмическая парадигма: жадная
Сложность времени: O (N 2 ) где N — количество человек.

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

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

Минимизируйте денежный поток среди данного набора друзей, которые одолжили деньги друг у друга

0.00 (0%) 0 votes