ধরুন কয়েকজন বন্ধু আছে। তারা একে অপরের কাছ থেকে টাকা ধার করেছে। তাই নেটওয়ার্কে কিছু নগদ প্রবাহ থাকবে। আমাদের কাজ হল নেটওয়ার্কে নগদ প্রবাহ কমিয়ে আনা। ধরুন তিনজন বন্ধু আছে P1, P2 এবং P3। তাদের মধ্যে নগদ প্রবাহ নিচের মত -
এই নগদ প্রবাহ সর্বনিম্ন নয়; আমাদের এটা কমাতে হবে। তারপর চূড়ান্ত চিত্রটি −
এর মত হবে
এই সমস্যা সমাধানের জন্য আমরা লোভী পন্থা ব্যবহার করব। এখানে প্রতিটি ধাপে একজন ব্যক্তির সমস্ত পরিমাণ নিষ্পত্তি করুন এবং অবশিষ্ট n-1 ব্যক্তির জন্য পুনরাবৃত্তি করুন। এখন প্রশ্ন আসে, প্রথম ব্যক্তি কীভাবে নির্বাচন করবেন? উত্তর হল, প্রতিটি ব্যক্তির জন্য নিট পরিমাণ গণনা করুন যেখানে সমস্ত ক্রেডিট থেকে সমস্ত ঋণ বিয়োগ করে নেট পরিমাণ পাওয়া যায়। যখন নেট পরিমাণ মূল্যায়ন করা হয়, তখন সর্বনিম্ন এবং সর্বোচ্চ দুটি নোড খুঁজুন। এই দুই ব্যক্তি সর্বাধিক পাওনাদার এবং দেনাদার। ন্যূনতম মানসম্পন্ন ব্যক্তি প্রথম ব্যক্তি। অ্যালগরিদম নিচের মত -
-
প্রতিটি ব্যক্তির জন্য Pi, 0 থেকে n – 1 পর্যন্ত, নিম্নলিখিত পদক্ষেপগুলি করুন
-
প্রতিটি ব্যক্তির জন্য নেট পরিমাণ গণনা করুন। একজন ব্যক্তির জন্য নেট মাউন্ট সব ক্রেডিট থেকে সমস্ত ঋণের যোগফল বিয়োগ করে গণনা করা যেতে পারে।
-
সর্বাধিক পাওনাদার পিসি এবং সর্বাধিক দেনাদার পিডি খুঁজুন। ধরুন একজন সর্বোচ্চ পাওনাদারের কাছে ক্রেডিট করা সর্বাধিক পরিমাণ হল max_credit, এবং সর্বাধিক দেনাদার থেকে ডেবিট করা সর্বাধিক পরিমাণকে max_debit বলা হয়।
-
সেট x:=সর্বনিম্ন সর্বোচ্চ_ক্রেডিট এবং সর্বোচ্চ_ডেবিট। তারপরে Pd থেকে x ডেবিট করুন এবং x কে Pc এ ক্রেডিট করুন
-
যদি 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
