สมมุติว่ามีเพื่อนไม่กี่คน พวกเขายืมเงินซึ่งกันและกัน ดังนั้นจะมีกระแสเงินสดบางส่วนในเครือข่าย งานของเราคือการลดกระแสเงินสดในเครือข่าย สมมติว่ามีเพื่อนสามคน P1, P2 และ P3 กระแสเงินสดในหมู่พวกเขาเป็นดังนี้ -
กระแสเงินสดนี้ไม่ใช่ขั้นต่ำ เราต้องย่อให้เล็กสุด จากนั้นไดอะแกรมสุดท้ายจะเป็นเช่น −
เพื่อแก้ปัญหานี้เราจะใช้วิธีโลภ ที่นี่ในแต่ละขั้นตอนจะชำระจำนวนเงินทั้งหมดสำหรับหนึ่งคนและเกิดขึ้นอีกสำหรับ n-1 คนที่เหลืออยู่ มาถึงคำถามว่า จะเลือกคนแรกยังไงดี? คำตอบคือ ให้คำนวณจำนวนเงินสุทธิของทุกๆ คนที่ได้รับยอดสุทธิโดยการหักหนี้ทั้งหมดออกจากเครดิตทั้งหมด เมื่อคำนวณจำนวนเงินสุทธิแล้ว ให้หาโหนดสองโหนดซึ่งมีค่าต่ำสุดและสูงสุด บุคคลสองคนนี้เป็นเจ้าหนี้และลูกหนี้ส่วนใหญ่ บุคคลที่มีค่าต่ำสุดคือคนแรก อัลกอริทึมเป็นเหมือนด้านล่าง −
-
สำหรับทุกคน Pi จาก 0 ถึง n – 1 ทำตามขั้นตอนต่อไปนี้
-
คำนวณจำนวนเงินสุทธิสำหรับทุกคน Net mount สำหรับบุคคลที่ฉันสามารถคำนวณได้โดยการลบผลรวมของหนี้ทั้งหมดออกจากผลรวมของเครดิตทั้งหมด
-
ค้นหา Pc เจ้าหนี้สูงสุดและ Pd ลูกหนี้สูงสุด สมมติว่าจำนวนเงินสูงสุดที่จะให้เครดิตแก่เจ้าหนี้สูงสุดคือ max_credit และจำนวนเงินสูงสุดที่หักจากลูกหนี้สูงสุดเรียกว่า max_debit
-
set x:=ขั้นต่ำของ max_credit และ max_debit จากนั้นเดบิต x จาก Pd และให้เครดิต 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
