मान लीजिए कुछ दोस्त हैं। उन्होंने एक-दूसरे से पैसे उधार लिए हैं। तो नेटवर्क पर कुछ नकदी प्रवाह होगा। हमारा काम नेटवर्क में नकदी प्रवाह को कम करना है। मान लीजिए कि तीन मित्र P1, P2 और P3 हैं। उनमें से नकदी प्रवाह नीचे जैसा है -
यह नकदी प्रवाह न्यूनतम नहीं है; हमें इसे कम करना होगा। तब अंतिम आरेख इस प्रकार होगा -
इस समस्या को हल करने के लिए हम लालची दृष्टिकोण का उपयोग करेंगे। यहां प्रत्येक चरण में एक व्यक्ति की सभी राशियों का निपटान करें और शेष n-1 व्यक्तियों के लिए पुनरावृत्ति करें। अब सवाल आता है कि पहले व्यक्ति को कैसे चुनें? उत्तर है, प्रत्येक व्यक्ति के लिए शुद्ध राशि की गणना करें जहां सभी ऋणों को सभी क्रेडिट से घटाकर शुद्ध राशि प्राप्त की जाती है। जब शुद्ध राशि का मूल्यांकन किया जाता है, तो दो नोड्स खोजें जो न्यूनतम और अधिकतम हों। ये दो व्यक्ति सबसे अधिक लेनदार और देनदार हैं। न्यूनतम मान वाला व्यक्ति पहला व्यक्ति होता है। एल्गोरिथ्म नीचे जैसा है -
-
प्रत्येक व्यक्ति पाई के लिए, 0 से n-1 तक, निम्न चरणों का पालन करें
-
प्रत्येक व्यक्ति के लिए शुद्ध राशि की गणना करें। एक व्यक्ति के लिए नेट माउंट I की गणना सभी ऋणों के योग को सभी क्रेडिट के योग से घटाकर की जा सकती है।
-
अधिकतम लेनदार पीसी और अधिकतम देनदार पीडी खोजें। मान लीजिए कि अधिकतम लेनदार को क्रेडिट की जाने वाली अधिकतम राशि max_credit है, और अधिकतम देनदार से डेबिट की गई अधिकतम राशि को max_debit कहा जाता है।
-
सेट x:=न्यूनतम अधिकतम_क्रेडिट और अधिकतम_डेबिट। फिर पीडी से x डेबिट करें, और 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