Giảm thiểu Dòng tiền giữa một nhóm bạn bè nhất định đã vay tiền của nhau trong C ++

Giả sử có ít bạn bè. Họ đã vay tiền của nhau. Vì vậy, sẽ có một số dòng tiền trên mạng. Nhiệm vụ của chúng tôi là giảm thiểu dòng tiền trong mạng lưới. Giả sử có ba bạn P1, P2, P3. Dòng tiền giữa chúng như sau -

Dòng tiền này không phải là tối thiểu; chúng ta phải giảm thiểu nó. Sau đó, sơ đồ cuối cùng sẽ như thế này -

Để giải quyết vấn đề này, chúng ta sẽ sử dụng phương pháp tham lam. Ở đây trong mỗi bước giải quyết tất cả số tiền của một người và định kỳ cho n-1 người còn lại. Bây giờ câu hỏi đến, làm thế nào để chọn người đầu tiên? Câu trả lời là, hãy tính số tiền ròng cho mỗi người mà số tiền ròng thu được bằng cách trừ tất cả các khoản nợ cho tất cả các khoản tín dụng. Khi số tiền ròng được đánh giá, sau đó tìm hai nút nhỏ nhất và lớn nhất. Hai người này hầu hết là chủ nợ và con nợ. Người có giá trị nhỏ nhất là người đầu tiên. Thuật toán như dưới đây -

• Đối với mỗi người Pi, từ 0 đến n - 1, hãy thực hiện các bước sau

• Tính số tiền thực cho mỗi người. Giá trị thực của một người mà tôi có thể được tính bằng cách lấy tổng tất cả các khoản tín dụng trừ đi tổng số nợ.

• Tìm chủ nợ tối đa Pc và con nợ tối đa Pd. Giả sử số tiền tối đa được ghi có cho một chủ nợ tối đa là max_credit và số tiền tối đa được ghi nợ từ một con nợ tối đa được gọi là max_debit.

• đặt x:=tối thiểu của max_credit và max_debit. Sau đó ghi nợ x từ Pd và ghi có x thành Pc

• Nếu x giống với max_credit, thì hãy xóa Pc khỏi tập hợp và lặp lại cho n-1 người tiếp theo.

• nếu x giống với max_debit, thì hãy xóa Pd khỏi một nhóm người và lặp lại cho n-1 người tiếp theo

Ví dụ

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

Đầu ra

P1 sends 4000 to P2
P0 sends 3000 to P2