Cân bằng tài khoản tối ưu trong C ++

Giả sử một nhóm bạn đi nghỉ và đôi khi họ cho nhau vay tiền. Ví dụ, Amit đã trả cho bữa trưa của Bikram với giá 10 đô la. Sau đó, Chandan đưa cho Amit 5 đô la tiền taxi. Chúng tôi phải thiết kế một mô hình trong đó mỗi giao dịch được lấy dưới dạng một bộ (x, y, z) có nghĩa là người x đã cho người y $ z.

Giả sử Amit, Bikram và Chandan lần lượt là người 0, 1 và 2, các giao dịch có thể được biểu diễn dưới dạng [[0, 1, 10], [2, 0, 5]]. Nếu chúng tôi có danh sách các giao dịch giữa một nhóm người, chúng tôi phải tìm số lượng giao dịch tối thiểu cần thiết để giải quyết khoản nợ.

Vì vậy, nếu đầu vào là [[0,1,10], [2,0,5]], thì đầu ra sẽ là 2, vì người # 0 đã cho người # 1 là 10 đô la. Sau đó, người số 2 đã cho người thứ # 0 $ 5. Ở đây cần có hai giao dịch. Một cách để giải quyết khoản nợ là người số 1 trả cho người số 0 và số 2 mỗi người 5 đô la.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

Xác định một mảng v
Xác định một hàm dfs (), hàm này sẽ lấy idx,
ret:=inf
while (idx
- (tăng idx lên 1)
để khởi tạo i:=idx + 1, khi i - kích thước của v, cập nhật (tăng i lên 1), thực hiện -
- nếu v [i] * v [idx] <0, thì -
  - v [i]:=v [i] + v [idx]
  - ret:=tối thiểu ret và 1 + dfs (idx + 1)
  - v [i]:=v [i] - v [idx]
return (nếu ret giống với inf thì 0, nếu không thì ret)
Từ phương thức chính, thực hiện như sau -
Xác định một bản đồ m
n:=kích thước của t
để khởi tạo i:=0, khi i
- u:=t [i, 0], v:=t [i, 1]
- bal:=t [i, 2]
- m [u]:=m [u] + bal
- m [v]:=m [v] - kiện
đối với mỗi cặp khóa-giá trị i trong m, do -
- nếu giá trị của tôi, thì -
  - chèn giá trị của i vào cuối v
- (tăng tôi lên 1)
trả về tối thiểu dfs (0) và kích thước v

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Cân bằng tài khoản tối ưu trong C ++

Ví dụ

Đầu vào

Đầu ra