資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中最小化給定朋友集之間的現金流（朋友之間互相借錢）
假設有一些朋友。他們之間互相借錢。所以在網路上會有一些現金流。我們的任務是最小化網路中的現金流。假設有三個朋友 P1、P2 和 P3。他們之間的現金流如下所示：
此現金流不是最小的；我們必須將其最小化。然後最終圖將如下所示：
為了解決這個問題，我們將使用貪心演算法。在這裡，在每一步中，我們都會結算一個人的所有金額，並對剩下的 n-1 個人進行遞迴。現在問題來了，如何選擇第一個人？答案是，計算每個人的淨額，其中淨額是透過從所有貸方中減去所有借方獲得的。當評估淨額時，然後找到兩個最小和最大的節點。這兩個節點分別是最大的債權人和債務人。具有最小值的人是第一個人。演算法如下所示：
對於每個人 Pi，從 0 到 n – 1，執行以下步驟
計算每個人的淨額。一個人的淨額可以透過從所有借方的總和中減去所有貸方的總和來計算。
找到最大的債權人 Pc 和最大的債務人 Pd。假設要貸給最大債權人的最大金額為 max_credit，而從最大債務人那裡借出的最大金額稱為 max_debit。
設定 x：= max_credit 和 max_debit 中的最小值。然後從 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
更新於： 2019 年 10 月 22 日
979 次檢視
廣告