मान लीजिए दोस्तों का एक समूह छुट्टी पर गया और कभी-कभी उन्होंने एक-दूसरे को पैसे उधार दिए। तो उदाहरण के लिए, अमित ने बिक्रम के दोपहर के भोजन के लिए $10 का भुगतान किया। फिर बाद में चंदन ने अमित को टैक्सी किराए के लिए $5 दिए। हमें एक मॉडल डिज़ाइन करना है जहां प्रत्येक लेनदेन को एक टपल (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 के आकार से कम है और v[idx] शून्येतर नहीं है), करें −
(idx को 1 से बढ़ाएं)
i := idx + 1 से आरंभ करें, जब i − v का आकार, अद्यतन करें (i को 1 से बढ़ाएं), करें −
यदि v[i] * v[idx] < 0, तो −
v[i] := v[i] + v[idx]
ret := ret और 1 + dfs(idx + 1) का न्यूनतम
v[i] := v[i] - v[idx]
लौटाएं (यदि ret, inf के समान है, तो 0, अन्यथा ret)
मुख्य विधि से निम्नलिखित करें −
एक मैप m परिभाषित करें
n := t का आकार
i := 0 से आरंभ करें, जब i < n, अद्यतन करें (i को 1 से बढ़ाएं), करें −
u := t[i, 0], v := t[i, 1]
bal := t[i, 2]
m[u] := m[u] + bal
m[v] := m[v] - bal
m में प्रत्येक कुंजी-मान जोड़ी i के लिए, करें −
यदि i का मान, तो −
i के मान को v के अंत में डालें
(i को 1 से बढ़ाएं)
dfs(0) और v के आकार का न्यूनतम लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<int> 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<vector<int>>&t) { map<int, int> 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<int, int>::iterator i = m.begin(); while (i != m.end()) { if (i->second) v.push_back(i->second); i++; } return min(dfs(0), (int)v.size()); } }; main() { Solution ob; vector<vector<int>> v = {{0,1,10},{2,0,5}}; cout << (ob.minTransfers(v)); }इनपुट
{{0,1,10},{2,0,5}}आउटपुट
2
