친구가 거의 없다고 가정해 봅시다. 그들은 서로 돈을 빌렸습니다. 따라서 네트워크에는 약간의 현금 흐름이 있습니다. 우리의 임무는 네트워크의 현금 흐름을 최소화하는 것입니다. 세 친구 P1, P2, P3가 있다고 가정합니다. 그들 사이의 현금 흐름은 다음과 같습니다 -
이 현금 흐름은 최소가 아닙니다. 최소화해야 합니다. 그러면 최종 다이어그램은 다음과 같습니다. -
이 문제를 해결하기 위해 greedy 접근 방식을 사용합니다. 여기 각 단계에서 한 사람의 모든 금액을 정산하고 나머지 n-1명에 대해 반복합니다. 이제 질문이 옵니다. 첫 번째 사람을 선택하는 방법은 무엇입니까? 답은 모든 크레딧에서 모든 부채를 빼서 순 금액을 얻은 모든 사람의 순 금액을 계산하는 것입니다. 순 금액이 평가되면 최소값과 최대값인 두 개의 노드를 찾으십시오. 이 두 사람이 대부분의 채권자이자 채무자입니다. 최소값을 가진 사람이 첫 번째 사람입니다. 알고리즘은 아래와 같습니다 -
-
모든 사람 Pi에 대해 0에서 n – 1까지 다음 단계를 수행하십시오.
-
모든 사람의 순 금액을 계산합니다. 사람의 순 가산액은 모든 크레딧 합계에서 모든 부채 합계를 빼서 계산할 수 있습니다.
-
최대 채권자 Pc와 최대 채무자 Pd를 구합니다. 최대 채권자에게 적립되는 최대 금액이 max_credit이고 최대 채무자로부터 인출되는 최대 금액을 max_debit이라고 가정합니다.
-
x:=max_credit 및 max_debit의 최소값을 설정합니다. 그런 다음 Pd에서 x를 인출하고 Pc에 x를 입금합니다.
-
x가 max_credit와 같으면 집합에서 Pc를 제거하고 다음 n-1명에 대해 반복합니다.
-
x가 max_debit와 같으면 사람 집합에서 Pd를 제거하고 다음 n-1명에 대해 반복됩니다.
예시
#include<iostream>
#include<algorithm>
#define N 3
using namespace std;
int getMinIndex(int arr[]) {
int minInd = 0;
for (int i=1; i<N; i++)
if (arr[i] < arr[minInd])
minInd = i;
return minInd;
}
int getMaxIndex(int arr[]) {
int maxInd = 0;
for (int i=1; i<N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
void cashFlowTask(int amount[]) {
int max_credit = getMaxIndex(amount), max_debit = getMinIndex(amount);
if (amount[max_credit] == 0 && amount[max_debit] == 0)
return;
int min_val = min(-amount[max_debit], amount[max_credit]);
amount[max_credit] -= min_val;
amount[max_debit] += min_val;
cout << "P" << max_debit << " sends " << min_val << " to " << "P" << max_credit << endl;
cashFlowTask(amount);
}
void minCashFlow(int graph[][N]) {
int amount[N] = {0};
for (int p=0; p<N; p++)
for (int i=0; i<N; i++)
amount[p] += (graph[i][p] - graph[p][i]);
cashFlowTask(amount);
}
int main() {
int graph[N][N] = {
{0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0},};
minCashFlow(graph);
} 출력
P1 sends 4000 to P2 P0 sends 3000 to P2