C++-এ আপ্টিমাল অ্যাকাউন্ট ব্যালেন্সিং (Optimal Account Balancing)

ধরি বন্ধুদের একটি গোষ্ঠী পিকনিকে গেল এবং কখনো কখনো একে অপরকে টাকা ঋণ দিল। উদাহরণস্বরূপ, অমিত বিক্রমের লঞ্চের জন্য ১০ ডলার দিল। পরে চন্দন অমিতকে ট্যাক্সির ভাড়া ৫ ডলার দিল। আমাদের একটি মডেল ডিজাইন করতে হবে যেখানে প্রতিটি ট্রানজ্যাকশন একটি টাপল (x, y, z) হিসেবে নেওয়া হবে যার মানে হল ব্যক্তি x ব্যক্তি yকে $z দিয়েছে।

যদি অমিত, বিক্রম, এবং চন্দন যথাক্রমে ব্যক্তি 0, 1, এবং 2 হন, তবে ট্রানজ্যাকশনগুলো হবে [[0, 1, 10], [2, 0, 5]]। যদি মানুষের একটি গোষ্ঠীর মধ্যে ট্রানজ্যাকশনগুলো দেওয়া থাকে, তবে ঋণ चुकाয়ের জন্য প্রয়োজনীয় ন্যূনতম ট্রানজ্যাকশনের সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট [[0,1,10], [2,0,5]] হলে আউটপুট হবে 2। কারণ ব্যক্তি #0 ব্যক্তি #1 কে $10 দিল। তারপর ব্যক্তি #2 ব্যক্তি #0 কে $5 দিল। এখানে দুটি ট্রানজ্যাকশন প্রয়োজন। ঋণ चुकाয়ের একটি উপায় হল ব্যক্তি #1 ব্যক্তি #0 এবং #2 কে $5 করে দেবে।

সমাধানের ধাপসমূহ

একটি অ্যারে v সংজ্ঞায়িত করা।
dfs() ফাংশন সংজ্ঞায়িত করা: এটি idx নিবে।
- ret := INF
- যখন (idx < v.size() এবং v[idx] == 0): idx++
- i = idx + 1 থেকে v.size()-1 পর্যন্ত লুপ:
  - যদি v[i] * v[idx] < 0:
    - v[i] := v[i] + v[idx]
    - ret := min(ret, 1 + dfs(idx + 1))
    - v[i] := v[i] - v[idx]
- ফেরত: (ret == INF ? 0 : ret)
মেইন মেথড থেকে:
- একটি ম্যাপ m সংজ্ঞায়িত করা।
- n := t.size()
- i = 0 থেকে n-1 পর্যন্ত লুপ:
  - u := t[i][0], v := t[i][1]
  - bal := t[i][2]
  - m[u] += bal; m[v] -= bal
- m-র প্রতিটি key-value pair জন্য:
  - যদি value != 0 হয়, তবে v-তে value পুশ করা।
- ফেরত: min(dfs(0), v.size())

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector v;
    int dfs(int idx) {
        int ret = INT_MAX;
        while (idx < v.size() && !v[idx])
            idx++;
        for (int i = idx + 1; i < v.size(); i++) {
            if (v[i] * v[idx] < 0) {
                v[i] += v[idx];
                ret = min(ret, 1 + dfs(idx + 1));
                v[i] -= v[idx];
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
    int minTransfers(vector>& t) {
        map m;
        int n = t.size();
        for (int i = 0; i < n; i++) {
            int u = t[i][0];
            int v = t[i][1];
            int bal = t[i][2];
            m[u] += bal;
            m[v] -= bal;
        }
        map::iterator i = m.begin();
        while (i != m.end()) {
            if (i->second)
                v.push_back(i->second);
            i++;
        }
        return min(dfs(0), (int)v.size());
    }
};

int main() {
    Solution ob;
    vector> v = {{0,1,10},{2,0,5}};
    cout << (ob.minTransfers(v));
}

ইনপুট

{{0,1,10},{2,0,5}}