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