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